The sequence a_1,...,a_m is a common subsequence in the set of permutations S = p_1,...,p_k on [n] if it is a subsequence of p_i(1),...,p_i(n) and p_j(1),...,p_j(n) for some distinct p_i, p_j in S. Recently, Beame and Huynh-Ngoc (2008) showed that when k>=3, every set of k permutations on [n] has a common subsequence of length at least n^ 1 3 . We show that, surprisingly, this lower bound is asymptotically optimal for all constant values of k. Specifically, we show that for any k>=3 and n>=k^2 there exists a set of k permutations on [n] in which the longest common subsequence has length at most 32(kn)^ 1 3 . The proof of the upper bound is constructive, and uses elementary algebraic techniques.
There has been extensive research on error-correcting codes built over a metric space defined by a deletion distance @cite_12 @cite_9 @cite_6 @cite_7 , and on codes built over the symmetric group @math @cite_1 @cite_5 @cite_10 @cite_8 . As far as we know, however, our result is the first to explicitly provide bounds on the capabilities of error-correcting codes built over @math .
@cite_7 @cite_8 @cite_9 @cite_1 @cite_6 @cite_5 @cite_10 @cite_12
1512964282 2125889434 2341012151 2963754880
The problem of error-control in a "noncoherent" random network coding channel is considered. Information transmission is modelled as the injection into the network of a basis for a vector space V and the collection by the receiver of a basis for a vector space U. A suitable coding metric on subspaces is defined, under which a minimum distance decoder achieves correct decoding if the dimension of the space V U is large enough. When the dimension of each codeword is restricted to a fixed integer, the code forms a subset of the vertices of the Grassmann graph. Sphere-packing, sphere-covering bounds and a Singleton bound are provided for such codes. A Reed-Solomon-like code construction is provided and decoding algorithm given. The results of this paper can be stated in three equivalent ways—in terms of the sparse recovery problem, the error-correction problem, and the problem of existence of certain extremal (neighborly) polytopes. Error-correcting codes are used in modern technology to protect information from errors. Information is formed by finite words over some alphabet F. The encoder transforms an n-letter word x into an m-letter word y with m>n . The decoder must be able to recover x correctly when up to r letters of y are corrupted in any way. Such an encoder-decoder pair is called an (n, m, r)-error-correcting code. Development of algorithmically efficient error correcting codes has attracted attention of engineers, computer scientists, and applied mathematicians for the past five decades. Known constructions involve deep algebraic and combinatorial methods, see [34, 35, 36]. This paper develops an approach to error-correcting codes from the viewpoint of geometric functional analysis (asymptotic convex geometry). It thus belongs to a common ground of coding theory, signal processing, combinatorial geometry, and geometric functional analysis. Our argument, outlined in Section 3, may be of independent interest in geometric functional analysis. Our main focus will be on words over the alphabet F = R or C. In applications, these words may be formed of the coefficients of some signal (such as image or audio) Maximum distance separable (MDS) codes are optimal error-correcting codes in the sense that they provide the maximum failure-tolerance for a given number of parity nodes. Suppose that an MDS code with @math information nodes and @math parity nodes is used to encode data in a distributed storage system. It is known that if @math out of the @math nodes are inaccessible and @math surviving (helper) nodes are used to recover the lost data, then we need to download at least @math fraction of the data stored in each of the helper nodes (Dimakis et. al., 2010 and , 2013). If this lower bound is achieved for the repair of any @math erased nodes from any @math helper nodes, we say that the MDS code has the @math -optimal repair property. We study high-rate MDS array codes with the optimal repair property. Explicit constructions of such codes in the literature are only available for the cases where there are at most 3 parity nodes, and these existing constructions can only optimally repair a single node failure by accessing all the surviving nodes. In this paper, given any @math and @math , we present two explicit constructions of MDS array codes with the @math -optimal repair property for all @math and @math simultaneously. Codes in the first family can be constructed over any base field @math as long as @math where @math The encoding, decoding, repair of failed nodes, and update procedures of these codes all have low complexity. Codes in the second family have the optimal access property and can be constructed over any base field @math as long as @math Moreover, both code families have the optimal error resilience capability when repairing failed nodes. We also construct several other related families of MDS codes with the optimal repair property. Maximum distance separable (MDS) codes are optimal error-correcting codes in the sense that they provide the maximum failure tolerance for a given number of parity nodes. Suppose that an MDS code with @math information nodes and @math parity nodes is used to encode data in a distributed storage system. It is known that if @math out of the @math nodes are inaccessible and @math surviving (helper) nodes are used to recover the lost data, then we need to download at least @math fraction of the data stored in each of the helper nodes ( , 2010 and , 2013). If this lower bound is achieved for the repair of any @math erased nodes from any @math helper nodes, we say that the MDS code has the @math -optimal repair property. We study high-rate MDS array codes with the optimal repair property (also known as minimum storage regenerating codes, or MSR codes). Explicit constructions of such codes in the literature are only available for the cases where there are at most three parity nodes, and these existing constructions can only optimally repair a single node failure by accessing all the surviving nodes. In this paper, given any @math and @math , we present two explicit constructions of MDS array codes with the @math -optimal repair property for all @math and @math simultaneously. Codes in the first family can be constructed over any base field @math as long as @math , where @math . The encoding, decoding, repair of failed nodes, and update procedures of these codes all have low complexity. Codes in the second family have the optimal access property and can be constructed over any base field @math as long as @math . Moreover, both code families have the optimal error resilience capability when repairing failed nodes. We also construct several other related families of MDS codes with the optimal repair property.