New Quasi-cyclic Degenerate Linear Codes over GF(8)

Let [n, k, d] _q code be a linear code of length n, dimension k, and minimum Hamming distance d over GF(q). One of the most important problems in coding theory is to construct codes with best possible minimum distances. Recently, quasi-cyclic (QC) codes were proved to contain many such codes. In this paper, twenty-five new codes over GF(8) are constructed, which improve the best known lower bounds on minimum distance.     

The Nonexistence of Ternary [284, 6, 188] Codes

Let [n, k, d] _q codes be linear codes of length n, dimension k, and minimum Hamming distance d over GF(q). Let n _q (k, d) be the smallest value of n for which there exists an [n, k, d] _q code. It is known from [1, 2] that 284 n ₃(6, 188) 285 and 285 n ₃(6, 189) 286. In this paper, the nonexistence of [284, 6, 188]₃ codes is proved, whence we get n ₃(6, 188) = 285 and n ₃(6, 189) = 286.     

New Minimum Distance Bounds for Linear Codes over Small Fields

Let [n, k, d] _q -codes be linear codes of length n, dimension k, and minimum Hamming distance d over GF(q). In this paper we consider codes over GF(3), GF(5), GF(7), and GF(8). Over GF(3), three new linear codes are constructed. Over GF(5), eight new linear codes are constructed and the nonexistence of six codes is proved. Over GF(7), the existence of 33 new codes is proved. Over GF(8), the existence of ten new codes and the nonexistence of six codes is proved. All of these results improve the corresponding lower and upper bounds in Brouwer's table [www.win.tue.nl/aeb/voorlincod.html].     

Asymmetric quantum Reed-Solomon and generalized Reed-Solomon codes

Two new families of asymmetric quantum codes are constructed in this paper. The first one is derived from the Calderbank-Shor-Steane (CSS) construction applied to classical Reed-Solomon (RS) codes, providing quantum codes with parameters [[N = l(q ^l −1), K = l(q ^l −2d + c + 1), d _z ≥ d/d _x ≥ (d−c)]] _q , where q is a prime power and d > c + 1, c ≥ 1, l ≥ 1 are integers. The second family is derived from the CSS construction applied to classical generalized RS codes, generating quantum codes with parameters [[N = mn, K = m(2k−n + c), d _z ≥ d/d _x ≥ (d−c)]] _q , where q is a prime power, 1 < k < n < 2k + c ≤ q ^m , k = n − d + 1, and n, d > c + 1, c ≥ 1, m ≥ 1 are integers. Although the second proposed construction generalizes the first one, the techniques developed in both constructions are slightly different. These new codes have parameters better than or comparable to the ones available in the literature. Additionally, the proposed codes can be utilized in quantum channels having great asymmetry, that is, quantum channels in which the probability of occurrence of phase-shift errors is large when compared to the probability of occurrence of qudit-flip errors.     

Symmetric Rank Codes

As is well known, a finite field _n = GF(q ⁿ ) can be described in terms of n × n matrices A over the field = GF(q) such that their powers A ⁱ , i = 1, 2, ..., q ⁿ – 1, correspond to all nonzero elements of the field. It is proved that, for fields _n of characteristic 2, such a matrix A can be chosen to be symmetric. Several constructions of field-representing symmetric matrices are given. These matrices A ⁱ together with the all-zero matrix can be considered as a _n -linear matrix code in the rank metric with maximum rank distance d = n and maximum possible cardinality q ⁿ . These codes are called symmetric rank codes. In the vector representation, such codes are maximum rank distance (MRD) linear [n, 1, n] codes, which allows one to use known rank-error-correcting algorithms. For symmetric codes, an algorithm of erasure symmetrization is proposed, which considerably reduces the decoding complexity as compared with standard algorithms. It is also shown that a linear [n, k, d = n – k + 1] MRD code _k containing the above-mentioned one-dimensional symmetric code as a subcode has the following property: the corresponding transposed code is also _n -linear. Such codes have an extended capability of correcting symmetric errors and erasures.     

Special sequences as subcodes of reed-solomon codes

We consider sequences in which every symbol of an alphabet occurs at most once. We construct families of such sequences as nonlinear subcodes of a q-ary [n, k, n − k + 1] _q Reed-Solomon code of length n ≤ q consisting of words that have no identical symbols. We introduce the notion of a bunch of words of a linear code. For dimensions k ≤ 3 we obtain constructive lower estimates (tight bounds in a number of cases) on the maximum cardinality of a subcode for various n and q, and construct subsets of words meeting these estimates and bounds. We define codes with words that have no identical symbols, observe their relation to permutation codes, and state an optimization problem for them.     

On constructing disjoint linear codes

To produce a highly nonlinear resilient function, the disjoint linear codes were originally proposed by Johansson and Pasalic in IEEE Trans. Inform. Theory, 2003, 49(2): 494–501. In this paper, an effective method for finding a set of such disjoint linear codes is presented. When n ⩾ 2k, we can find a set of [n,k]disjoint linear codes with cardinality 2^n-k +⌊(n-k)/k⌊; When n < 2k, no set of disjoint linear codes exists with cardinality at least 2. We also describe a result on constructing a set of [n, k] disjoint linear codes with minimum distance at least some fixed positive integer.     

Approximate minimum weight matching on points ink-dimensional space

We study the problem of finding a minimum weight complete matching in the complete graph on a set V ofn points ink-dimensional space. The points are the vertices of the graph and the weight of an edge between any two points is the distance between the points under someL _q,-metric. We give anO((2c _q )^1.5k ?^?1.5k (α(n, n))^0.5 n ^1.5(logn)^2.5) algorithm for finding an almost minimum weight complete matching in such a graph, wherec _q =6k ^1/q for theL _q -metric, α is the inverse Ackermann function, and ? ≤ 1. The weight of the complete matching obtained by our algorithm is guaranteed to be at most (1 + ?) times the weight of a minimum weight complete matching.     

Some high-rate linear codes over <Emphasis Type="Italic">GF</Emphasis>(5) and <Emphasis Type="Italic">GF</Emphasis>(7)

Let an [n, k, d] _q code be a linear code of length n, dimension k, and with minimum Hamming distance d over GF(q). The ratio R = k/n is called the rate of a code. In this paper, [62, 53, 6]₅, [62, 48, 8]₅, [71, 56, 8]₅, [124, 113, 6]₅, [43, 36, 6]₇, [33, 23, 7]₇, and [27, 18, 7]₇ high-rate codes and new codes with parameters [42, 14, 19]₅, [42, 15, 18]₅, [48, 13, 24]₅, [52, 12, 28]₅, [71, 15, 38]₅, [71, 16, 36]₅, [72, 12, 41]₅, [78, 10, 50]₅, [88, 11, 54]₅, [88, 13, 51]₅, [124, 14, 77]₅, [32, 12, 15]₇, [32, 10, 17]₇, [36, 10, 20]₇, and [48, 10, 29]₇ are constructed. The codes with parameters [62, 53, 6]₅ and [43, 36, 6]₇ are optimal.     

Approximate minimum weight matching on points ink-dimensional space

We study the problem of finding a minimum weight complete matching in the complete graph on a set V ofn points ink-dimensional space. The points are the vertices of the graph and the weight of an edge between any two points is the distance between the points under someL _q,-metric. We give anO((2c _q )^{1.5k –1.5k} ((n, n))^0.5 n ^1.5(logn)^2.5) algorithm for finding an almost minimum weight complete matching in such a graph, wherec _q =6k ^1/q for theL _q -metric, is the inverse Ackermann function, and 1. The weight of the complete matching obtained by our algorithm is guaranteed to be at most (1 + ) times the weight of a minimum weight complete matching.This research was supported by a fellowship from the Shell Foundation.     

Complexity and Approximations for Multimessage Multicasting

We consider multimessage multicasting over thenprocessor complete (or fully connected) static network (MM_C). First we present a linear time algorithm that constructs for every degreedproblem instance a communication schedule with total communication time at mostd², wheredis the maximum number of messages that each processor may send or receive. Then we present degreedproblem instances such that all their communication schedules have total communication time at leastd². We observe that our lower bound applies when the fan-out (maximum number of processors receiving any given message) is huge, and thus the number of processors is also huge. Since this environment is not likely to arise in the near future, we turn our attention to the study of important subproblems that are likely to arise in practice. We show that when each message has fan-outk=1 theMM_Cproblem corresponds to the makespan openshop preemptive scheduling problem which can be solved in polynomial time and show that fork?2 our problem is NP-complete and remains NP-complete even when forwarding is allowed. We present an algorithm to generate a communication schedule with total communication time 2d−1 for any degreedproblem instance with fan-outk=2. Our main result is anO(q·d·e) time algorithm, wheree?nd(the input length), with an approximation bound ofqd+k^1/q(d−1), for any integerqsuch thatk>q?2. Our algorithms are centralized and require all the communication information ahead of time. Applications where all of this information is readily available include iterative algorithms for solving linear equations, and most dynamic programming procedures. The Meiko CS-2 machine and computer systems with processors communicating via dynamic permutation networks whose basic switches can act as data replicators (e.g.,nbynBenes network with 2 by 2 switches that can also act as data replicators) will also benefit from our results at the expense of doubling the number of communication phases.     

Bounds on the minimum code distance for nonbinary codes based on bipartite graphs

The minimum distance of codes on bipartite graphs (BG codes) over GF(q) is studied. A new upper bound on the minimum distance of BG codes is derived. The bound is shown to lie below the Gilbert-Varshamov bound when q ≤ 32. Since the codes based on bipartite expander graphs (BEG codes) are a special case of BG codes and the resulting bound is valid for any BG code, it is also valid for BEG codes. Thus, nonbinary (q ≤ 32) BG codes are worse than the best known linear codes. This is the key result of the work. We also obtain a lower bound on the minimum distance of BG codes with a Reed-Solomon constituent code and a lower bound on the minimum distance of low-density parity-check (LDPC) codes with a Reed-Solomon constituent code. The bound for LDPC codes is very close to the Gilbert-Varshamov bound and lies above the upper bound for BG codes.     

New Technique for Decoding Codes in the Rank Metric and Its Cryptography Applications

We present two new algorithms for decoding an arbitrary (n, k) linear rank distance code over GF(q ^N ). These algorithms correct errors of rank r in O((Nr)³ q ^(r–1)(k+1)) and O((k + r)³ r ³ q ^{(r–1)(N–r)}) operations in GF(q) respectively. The algorithms give one of the most efficient attacks on public-key cryptosystems based on rank codes, as well as on the authentication scheme suggested by Chen.     

On the efficiency of effective Nullstellensätze

Letk be an infinite and perfect field,x ₁, ...,x _n indeterminates overk and letf ₁, ...,f _s be polynomials ink[x ₁, ...,x _n ] of degree bounded by a given numberd, which satisfiesdn. We prove an effective affine Nullstellensatz of the following particular form:For arbitrary given parametersd, s, n there exists a probabilistic (randomized) arithmetic network overk of sizes ^O(1) d ^O(n) and depthO(n ⁴log² sd) solving the following task:     

Small Space Representations for Metric Min-sum k-Clustering and Their Applications

The min-sum k -clustering problem is to partition a metric space (P,d) into k clusters C ₁,…,C _k ?P such that $\sum_{i=1}^{k}\sum_{p,q\in C_{i}}d(p,q)The min-sum k -clustering problem is to partition a metric space (P,d) into k clusters C ₁,…,C _k ⊆P such that ?_i=1^k?_{p,q ? Ci}d(p,q)\sum_{i=1}^{k}\sum_{p,q\in C_{i}}d(p,q) is minimized. We show the first efficient construction of a coreset for this problem. Our coreset construction is based on a new adaptive sampling algorithm. With our construction of coresets we obtain two main algorithmic results.     

Inductive Constructions of Perfect Ternary Constant-Weight Codes with Distance 3

We propose inductive constructions of perfect (n,3;n – 1)₃ codes (ternary constant-weight codes of length n and weight n – 1 with distance 3), which are modifications of constructions of perfect binary codes. The construction yields at least different perfect (n,3;n – 1)₃ codes. To perfect (n,3;n – 1)₃ codes, perfect matchings in a binary hypercube without close (at distance 1 or 2 from each other) parallel edges are equivalent.     

Proper Learning Algorithm for Functions of k Terms under Smooth Distributions

In this paper, we introduce a probabilistic distribution, called a smooth distribution, which is a generalization of variants of the uniform distribution such as q-bounded distribution and product distribution. Then, we give an algorithm that, under the smooth distribution, properly learns the class of functions of k terms given as _k ^k_n={g(f₁(v), …, f_k(v)) | g _k, f₁, …, f_{k n}} in polynomial time for constant k, where _k is the class of all Boolean functions of k variables and _n is the class of terms over n variables. Although class _k ^k_n was shown by Blum and Singh to be learned using DNF as the hypothesis class, it has remained open whether it is properly learnable under a distribution-free setting.