Erasure Decoding for Gabidulin Codes

We present a new approach of the decoding algorithm for Gabidulin Codes. In the same way as efficient erasure decoding for Generalized Reed Solomon codes by using the structure of the inverse of the VanderMonde matrices, we show that, the erasure(t erasures mean that t components of a code vector are erased) decoding Gabidulin code can be seen as a computation of three matrice and an affine permutation, instead of computing an inverse from the generator or parity check matrix. This significantly reduces the decoding complexity compared to others algorithms. For t erasures with t ≤ r, where r = n − k, the erasure algorithm decoding for Gab _{n, k} (g) Gabidulin code compute the t symbols by simple multiplication of three matrices. That requires rt + r(k − 1) Galois field multiplications, t(r − 1) + (t + r)k field additions, r ² + r(k + 1) field negations and t(k + 1) field inversions.     

Distributions of Points in <Emphasis Type="Italic">d</Emphasis> Dimensions and Large <Emphasis Type="Italic">k</Emphasis>-Point Simplices

We consider a variant of Heilbronn’s triangle problem by investigating for a fixed dimension d≥2 and for integers k≥2 with k≤d distributions of n points in the d-dimensional unit cube [0,1] ^d , such that the minimum volume of the simplices, which are determined by (k+1) of these n points is as large as possible. Denoting by Δ _k,d (n), the supremum of this minimum volume over all distributions of n points in [0,1] ^d , we show that c _k,d ⋅(log n)^1/(d−k+1)/n ^k/(d−k+1)≤Δ _k,d (n)≤c _k,d ′/n ^k/d for fixed 2≤k≤d, and, moreover, for odd integers k≥1, we show the upper bound Δ _k,d (n)≤c _k,d ″/n ^{k/d+(k−1)/(2d(d−1))}, where c _k,d ,c _k,d ′,c _k,d ″>0 are constants. A preliminary version of this paper appeared in COCOON ’05.     

Dérivé convexe d’une loi de probabilité et lois stables. Application a un problème d’isomorphisme

The “convex derived set” of a symmetric probability lawF on the real line is defined as the set of limits of laws ∗ _j−1/k ⁿ F(t _j ⁿ η), inf 1≤j≤k _n t _j ⁿ →∞ ifn→∞ and the stable laws it contains are exhibited. A new criterion of stochastic compacity of the set of the powers of a probability law is established. Finally, an isomorphism theorem between somel ^p andL ⁰ spaces is given.

---

---

Laboratoire associé au C.N.R.S. n^o 224 “Processus stochastiques et applications”.     

Diagnostic tests for local coalescences of variables in Boolean functions

The article studies diagnostic tests for local k -fold coalescences of variables in Boolean functions f( [(x)\tilde]ⁿ )( 1 ￡ k ￡ n,  1 ￡ t ￡ 2^2k ) f\left( {{{\tilde{x}}^n}} \right)\left( {1 \leq k \leq n,\;1 \leq t \leq {2^{{2^k}}}} \right) . Upper and lower bounds are proved for the Shannon function of the length of the diagnostic test for local k -fold coalescences generated by the system of functions F_t^k \Phi_t^k . The Shannon function of the length of a complete diagnostic test for local k -fold coalescences behaves asymptotically as 2 ^k (n − k + 1) for n → ∞, k → ∞.     

Asymptotic results on infinite tandem queueing networks

We consider an infinite tandem queueing network consisting of ·/GI/1/∞ stations with i.i.d. service times. We investigate the asymptotic behavior of t(n, k), the inter-arrival times between customers n and n + 1 at station k, and that of w(n, k), the waiting time of customer n at station k. We establish a duality property by which w(n, k) and the “idle times”y(n, k) play symmetrical roles. This duality structure, interesting by itself, is also instrumental in proving some of the ergodic results. We consider two versions of the model: the quadrant and the half-plane. In the quadrant version, the sequences of boundary conditions {w(0,k), k∈ℕ} and {t(n, 0), n∈ℕ}, are given. In the half-plane version, the sequence {t(n, 0), n∈ℕ} is given. Under appropriate assumptions on the boundary conditions and on the services, we obtain ergodic results for both versions of the model. For the quadrant version, we prove the existence of temporally ergodic evolutions and of spatially ergodic ones. Furthermore, the process {t(n, k), n∈ℕ} converges weakly with k to a limiting distribution, which is invariant for the queueing operator. In the more difficult half plane problem, the aim is to obtain evolutions which are both temporally and spatially ergodic. We prove that 1/n∑ _k=1 ⁿ w(0, k) converges almost surely and in L ₁ to a finite constant. This constitutes a first step in trying to prove that {t(n,k), n∈ℤ} converges weakly with k to an invariant limiting distribution. Received: 23 March 1999 / Revised version: 5 January 2000 / Published online: 12 October 2000     

On the kernel and shortest face complexes in the unit cube

Studying the extreme kernel face complexes of a given dimension, we obtain some lower estimates of the number of shortest face complexes in the n-dimensional unit cube. The number of shortest complexes of k-dimensional faces is shown to be of the same logarithm order as the number of complexes consisting of at most 2 ⁿ⁻¹ different k-dimensional faces if 1 ≤ k ≤ c · n and c < 0.5. This implies similar lower bounds for the maximum length of the kernel DNFs and the number of the shortest DNFs of Boolean functions.     

Littlewood–Paley theorem on spaces <Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis>(<Emphasis Type="Italic">t</Emphasis>)</Superscript>(ℝ<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>)

We point out that if the Hardy–Littlewood maximal operator is bounded on the space L ^p(t)(ℝ), 1 < a ≤ p(t) ≤ b < ∞, t ∈ ℝ, then the well-known characterization of the spaces L ^p (ℝ), 1 < p < ∞, by the Littlewood–Paley theory extends to the space L ^p(t)(ℝ). We show that, for n > 1 , the Littlewood–Paley operator is bounded on L ^p(t) (ℝ ⁿ ), 1 < a ≤ p(t) ≤ b < ∞, t ∈ ℝ ⁿ , if and only if p(t) = const. Published in Ukrains’kyi Matematychnyi Zhurnal, Vol. 60, No. 12, pp. 1709–1715, December, 2008.     

The nearness problems for symmetric centrosymmetric with a special submatrix constraint

We say that X=[x_ij]_i,j=1ⁿX=[x_{ij}]_{i,j=1}^n is symmetric centrosymmetric if x _ij  = x _ji and x _{n − j + 1,n − i + 1}, 1 ≤ i,j ≤ n. In this paper we present an efficient algorithm for minimizing ||AXA ^T  − B|| where ||·|| is the Frobenius norm, A ∈ ℝ ^m×n , B ∈ ℝ ^m×m and X ∈ ℝ ^n×n is symmetric centrosymmetric with a specified central submatrix [x _ij ] _{p ≤ i,j ≤ n − p} . Our algorithm produces a suitable X such that AXA ^T  = B in finitely many steps, if such an X exists. We show that the algorithm is stable any case, and we give results of numerical experiments that support this claim.     

Multivariate Regression Depth

   Abstract. The regression depth of a hyperplane with respect to a set of n points in \Real ^d is the minimum number of points the hyperplane must pass through in a rotation to vertical. We generalize hyperplane regression depth to k -flats for any k between 0 and d-1 . The k=0 case gives the classical notion of center points. We prove that for any k and d , deep k -flats exist, that is, for any set of n points there always exists a k -flat with depth at least a constant fraction of n . As a consequence, we derive a linear-time (1+ɛ) -approximation algorithm for the deepest flat. We also show how to compute the regression depth in time O(n ^d-2 +nlog n) when 1≤ k≤ d-2 .     

A parallel algorithm for generating multiple ordering spanning trees in undirected weighted graphs

1.IntroductionLetG=(V,E,W)beaconnected,weightedandundirectedgraph,VeEE,w(e)(相似文献   

On K s -free subgraphs in K s+k -free graphs and vertex Folkman numbers

Extending the problem of determining Ramsey numbers Erdős and Rogers introduced the following function. For given integers 2 ≤ s < t let f _s,t (n) = min{max{|S|: S ⊆ V (H) and H[S] contains no K _s }}, where the minimum is taken over all K _t -free graphs H of order n. This function attracted a considerable amount of attention but despite that, the gap between the lower and upper bounds is still fairly wide. For example, when t=s+1, the best bounds have been of the form Ω(n ^1/2+o(1)) ≤ f _s,s+1(n) ≤ O(n ^1−ɛ(s)), where ɛ(s) tends to zero as s tends to infinity. In this paper we improve the upper bound by showing that f _s,s+1(n) ≤ O(n ^2/3). Moreover, we show that for every ɛ > 0 and sufficiently large integers 1 ≪ k ≪ s, Ω(n ^1/2−ɛ ) ≤ f _s,s+k (n) ≤ O(n ^1/2+ɛ . In addition, we also discuss some connections between the function f _s,t and vertex Folkman numbers.     

A sparse graph almost as good as the complete graph on points inK dimensions

A setV ofn points ink-dimensional space induces a complete weighted undirected graph as follows. The points are the vertices of this graph and the weight of an edge between any two points is the distance between the points under someL _p metric. Let ε≤1 be an error parameter and letk be fixed. We show how to extract inO(n logn+ε ^−k log(1/ε)n) time a sparse subgraphG=(V, E) of the complete graph onV such that: (a) for any two pointsx, y inV, the length of the shortest path inG betweenx andy is at most (1+∈) times the distance betweenx andy, and (b)|E|=O(ε^−k n).     

Orders on Multisets and Discrete Cones

We study additive representability of orders on multisets (of size k drawn from a set of size n) which satisfy the condition of independence of equal submultisets (IES) introduced by Sertel and Slinko (Ranking committees, words or multisets. Nota di Laboro 50.2002. Center of Operation Research and Economics. The Fundazione Eni Enrico Mattei, Milan, 2002, Econ. Theory 30(2):265–287, 2007). Here we take a geometric view of those orders, and relate them to certain combinatorial objects which we call discrete cones. Following Fishburn (J. Math. Psychol., 40:64–77, 1996) and Conder and Slinko (J. Math. Psychol., 48(6):425–431, 2004), we define functions f(n,k) and g(n,k) which measure the maximal possible deviation of an arbitrary order satisfying the IES and an arbitrary almost representable order satisfying the IES, respectively, from a representable order. We prove that g(n,k) = n − 1 whenever n ≥ 3 and (n, k) ≠ (5, 2). In the exceptional case, g(5,2) = 3. We also prove that g(n,k) ≤ f(n,k) ≤ n and establish that for small n and k the functions g(n,k) and f(n,k) coincide.      

Constructions of Spherical 3-Designs

 Spherical t-designs are Chebyshev-type averaging sets on the d-sphere which are exact for polynomials of degree at most t. This concept was introduced in 1977 by Delsarte, Goethals, and Seidel, who also found the minimum possible size of such designs, in particular, that the number of points in a 3-design on S ^d must be at least . In this paper we give explicit constructions for spherical 3-designs on S ^d consisting of n points for d=1 and ; d=2 and ; d=3 and ; d=4 and ; and odd or even. We also provide some evidence that 3-designs of other sizes do not exist. We will introduce and apply a concept from additive number theory generalizing the classical Sidon-sequences. Namely, we study sets of integers S for which the congruence mod n, where and , only holds in the trivial cases. We call such sets Sidon-type sets of strength t, and denote their maximum cardinality by s(n, t). We find a lower bound for s(n, 3), and show how Sidon-type sets of strength 3 can be used to construct spherical 3-designs. We also conjecture that our lower bound gives the true value of s(n, 3) (this has been verified for n≤125). Received: June 19, 1996     

An additive divisor problem with a growing number of factors

Let τk(n) be the number of representations ofn as the product ofk positive factors, τ(n)=τ(n). The asymptotics of Σ _n≤x τ _k (n)τ(n+1) for 80k ¹⁰ (lnlnx)³≤lnx is shown to be uniform with respect tok. Translated fromMatematicheskie Zametki, Vol. 61, No. 3, pp. 391–406, March, 1997. Translated by N. K. Kulman     

Existence of three HMOLS of type 2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript><Emphasis Type="Italic">u</Emphasis><Superscript>1</Superscript>

A Latin squares of order v with ni missing sub-Latin squares （holes） of order hi （1 〈= i 〈 k）, which are disjoint and spanning （i.e. ∑k i=l1 nihi = v）, is called a partitioned incomplete Latin squares and denoted by PILS. The type of PILS is defined by （h1n1 h2n2…hknk ）. If any two PILS inaset of t PILS of type T are orthogonal, then we denote the set by t-HMOLS（T）. It has been proved that 3-HMOLS（2n31） exist for n ≥6 with 11 possible exceptions. In this paper, we investigate the existence of 3-HMOLS（2nu1） with u ≥ 4, and prove that 3-HMOLS（2~u1） exist if n ≥ 54 and n ≥7/4u ＋ 7.     

<Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis></Superscript> Bounds for the Commutator of Parabolic Singular Integral with Rough Kernels

In this paper, the authors give the L ^p (1 < p < ∞ ) boundedness of the k-th order commutator of parabolic singular integral with the kernel function Ω ∈ L(log⁺ L) ^k + 1(S ^n − 1). The result in this paper is an extension of some known results. The research was supported by NSF of China (Grant: 10571015) and SRFDP of China (Grant: 20050027025).     

On the separation of maximally violated mod-k cuts

Separation is of fundamental importance in cutting-plane based techniques for Integer Linear Programming (ILP). In recent decades, a considerable research effort has been devoted to the definition of effective separation procedures for families of well-structured cuts. In this paper we address the separation of Chvátal rank-1 inequalities in the context of general ILP’s of the form min{c ^T x:Ax≤b,x integer}, where A is an m×n integer matrix and b an m-dimensional integer vector. In particular, for any given integer k we study mod-k cuts of the form λ ^T Ax≤⌊λ ^T b⌋ for any λ∈{0,1/k,...,(k−1)/k} ^m such that λ ^T A is integer. Following the line of research recently proposed for mod-2 cuts by Applegate, Bixby, Chvátal and Cook [1] and Fleischer and Tardos [19], we restrict to maximally violated cuts, i.e., to inequalities which are violated by (k−1)/k by the given fractional point. We show that, for any given k, such a separation requires O(mn min{m,n}) time. Applications to both the symmetric and asymmetric TSP are discussed. In particular, for any given k, we propose an O(|V|²|E ^*|)-time exact separation algorithm for mod-k cuts which are maximally violated by a given fractional (symmetric or asymmetric) TSP solution with support graph G ^*=(V,E ^*). This implies that we can identify a maximally violated cut for the symmetric TSP whenever a maximally violated (extended) comb inequality exists. Finally, facet-defining mod-k cuts for the symmetric and asymmetric TSP are studied. Received May 29, 1997 / Revised version received May 10, 1999?Published online November 9, 1999     

Partitioning Posets

Given a poset P = (X, ≺ ), a partition X ₁, ..., X _k of X is called an ordered partition of P if, whenever x ∈ X _i and y ∈ X _j with x ≺ y, then i ≤ j. In this paper, we show that for every poset P = (X, ≺ ) and every integer k ≥ 2, there exists an ordered partition of P into k parts such that the total number of comparable pairs within the parts is at most (m − 1)/k, where m ≥ 1 is the total number of edges in the comparability graph of P. We show that this bound is best possible for k = 2, but we give an improved bound, , for k ≥ 3, where c(k) is a constant depending only on k. We also show that, given a poset P = (X, ≺ ) and an integer 2 ≤ k ≤ |X|, we can find an ordered partition of P into k parts that minimises the total number of comparable pairs within parts in time polynomial in the size of P. We prove more general, weighted versions of these results. Supported by an EPSRC doctoral training grant.     

Laplacian Operators and Q-curvature on Conformally Einstein Manifolds

A new definition of canonical conformal differential operators P _k (k = 1,2,...), with leading term a kth power of the Laplacian, is given for conformally Einstein manifolds of any signature. These act between density bundles and, more generally, between weighted tractor bundles of any rank. By construction these factor into a power of a fundamental Laplacian associated to Einstein metrics. There are natural conformal Laplacian operators on density bundles due to Graham–Jenne–Mason–Sparling (GJMS). It is shown that on conformally Einstein manifolds these agree with the P _k operators and hence on Einstein manifolds the GJMS operators factor into a product of second-order Laplacian type operators. In even dimension n the GJMS operators are defined only for 1 ≤ k ≤ n/2 and so, on conformally Einstein manifolds, the P _k give an extension of this family of operators to operators of all even orders. For n even and k > n/2 the operators P _k are each given by a natural formula in terms of an Einstein metric but they are not natural conformally invariant operators in the usual sense. They are shown to be nevertheless canonical objects on conformally Einstein structures. There are generalisations of these results to operators between weighted tractor bundles. It is shown that on Einstein manifolds the Branson Q-curvature is constant and an explicit formula for the constant is given in terms of the scalar curvature. As part of development, conformally invariant tractor equations equivalent to the conformal Killing equation are presented.