We derive a linear programming bound on the maximum cardinality of error-correcting codes in the sum-rank metric. Based on computational experiments on relatively small instances, we observe that the obtained bounds o...
详细信息
We derive a linear programming bound on the maximum cardinality of error-correcting codes in the sum-rank metric. Based on computational experiments on relatively small instances, we observe that the obtained bounds outperform all previously known bounds.
We show how the Delsarte theory can be used to obtain a linear programming bound for orthogonal arrays with mixed levels. Even for strength 2 this improves on the Rao bound in a large number of cases. The results poin...
详细信息
We show how the Delsarte theory can be used to obtain a linear programming bound for orthogonal arrays with mixed levels. Even for strength 2 this improves on the Rao bound in a large number of cases. The results point to several interesting sets of parameters for which the existence of the arrays is at present undecided.
Based on an invariance-type property of the Lee-compositions of a linear Lee code, additional equality constraints can be introduced to the linearprogramming problem of linear Lee codes. In this paper, we formulate t...
详细信息
Based on an invariance-type property of the Lee-compositions of a linear Lee code, additional equality constraints can be introduced to the linearprogramming problem of linear Lee codes. In this paper, we formulate this property in terms of an action of the multiplicative group of the field F-q on the set of Lee-compositions. We show some useful properties of certain sums of Lee-numbers, which are the eigenvalues of the Lee association scheme, appearing in the linearprogramming problem of linear Lee codes. Using the additional equality constraints, we formulate the linearprogramming problem of linear Lee codes in a very compact form, leading to a fast execution, which allows to efficiently compute the bounds for large parameter values of the linear codes.
Delsarte et al. (Geom Dedicata 6:363-388, 1977) used the linearprogramming method in order to find bounds for the size of spherical codes endowed with prescribed inner products between distinct points in the code. In...
详细信息
Delsarte et al. (Geom Dedicata 6:363-388, 1977) used the linearprogramming method in order to find bounds for the size of spherical codes endowed with prescribed inner products between distinct points in the code. In this paper, we develop the linearprogramming method to obtain bounds for the number of vertices of connected regular graphs endowed with given distinct eigenvalues. This method is proved by some "dual" technique of the spherical case, motivated from the theory of association scheme. As an application of this bound, we prove that a connected k-regular graph satisfying has the minimum second-largest eigenvalue of all k-regular graphs of the same size, where d is the number of distinct non-trivial eigenvalues, and g is the girth. The known graphs satisfying are Moore graphs, incidence graphs of regular generalized polygons of order (s, s), triangle-free strongly regular graphs, and the odd graph of degree 4.
Orthogonal arrays (OAs) are basic combinatorial structures, which appear under various disguises in cryptology and the theory of algorithms. Among their applications are universal hashing, authentication codes, resili...
详细信息
Orthogonal arrays (OAs) are basic combinatorial structures, which appear under various disguises in cryptology and the theory of algorithms. Among their applications are universal hashing, authentication codes, resilient and correlation-immune functions, derandomization of algorithms, and perfect local randomizers. In this paper, we give new explicit bounds on the size of orthogonal arrays using Delsarte's linearprogramming method. Specifically, we prove that the minimum number of rows in a binary orthogonal array of length n and strength t is at least 2(n) - (n2(n-1)/t+1) and also at least 2(n) - (2(n-2)(n+1)/[t+1/2]). We also prove that these bounds are as powerful as the linear programming bound itself for many parametric situations. An (n, m, t)-resilient function is a function f : {0, 1}(n) --> {0, 1}(m) such that every possible output m-tuple is equally likely to occur when the values of t arbitrary inputs are fixed by an opponent and the remaining n-t input bits are chosen independently at random. A basic problem is to maximize t given m and n, i.e., to determine the largest value of t such that an (n, m, t)-resilient function exists. In this paper, we obtain upper and lower bounds for the optimal values of t where 1 less than or equal to n less than or equal to 25 and 1 less than or equal to m < n. The upper bounds are derived from Delsarte's linear programming bound, and the lower bounds come from constructions based on error-correcting codes. We also obtain new explicit upper bounds for the optimal values of t. It was proved by Chor et al. in [Proc. 26th IEEE Symp. on Foundations of Computer Science, 1985, pp. 396-407] that an (n,2,t)-resilient function exists if and only if t < [2n/3]. This result was generalized by Friedman [Proc. 33rd IEEE Symp. on Foundations ol Computer Science, 1992, pp. 314-319], who proved a bound for general m. We also prove some new bounds, and complete the determination of the optimal resiliency of resilient functions with m =
Multiply constant-weight codes (MCWCs) were introduced recently to improve the reliability of certain physically unclonable function response. In this paper, the bounds of MCWCs and the constructions of optimal MCWCs ...
详细信息
Multiply constant-weight codes (MCWCs) were introduced recently to improve the reliability of certain physically unclonable function response. In this paper, the bounds of MCWCs and the constructions of optimal MCWCs are studied. First, we derive three different types of upper bounds which improve the Johnson-type bounds given by Chee et al. for some parameters. The asymptotic lower bound of MCWCs is also examined. Then, we obtain the asymptotic existence of two classes of optimal MCWCs, which shows that the Johnson-type bounds for MCWCs with distances 2 Sigma(m)(i = 1) w(i) -2 or 2mw -2w are asymptotically exact. Finally, we construct a class of optimal MCWCs with total weight four and distance six by establishing the connection between such MCWCs and a new kind of combinatorial structures. As a consequence, the maximum sizes of MCWCs with total weight less than or equal to four are determined almost completely.
作者：
Roy, AidanScott, A. J.Univ Calgary
Dept Math & Stat Inst Quantum Informat Sci Calgary AB T2N 1N4 Canada Griffith Univ
Ctr Quantum Dynam Ctr Quantum Comp Technol Brisbane Qld 4111 Australia
A unitary design is a collection of unitary matrices that approximate the entire unitary group, much like a spherical design approximates the entire unit sphere. In this paper, we use irreducible representations of th...
详细信息
A unitary design is a collection of unitary matrices that approximate the entire unitary group, much like a spherical design approximates the entire unit sphere. In this paper, we use irreducible representations of the unitary group to find a general lower bound on the size of a unitary t-design in U(d), for any d and t. We also introduce the notion of a unitary code-a subset of U(d) in which the trace inner product of any pair of matrices is restricted to only a small number of distinct absolute values-and give an upper bound for the size of a code with s inner product values in U(d), for any d and s. These bounds can be strengthened when the particular inner product values that occur in the code or design are known. Finally, we describe some constructions of designs: we give an upper bound on the size of the smallest weighted unitary t-design in U(d), and we catalogue some t-designs that arise from finite groups.
We consider spherical codes attaining the Levenshtein upper bounds on the cardinality of codes with prescribed maximal inner product. We prove that the even Levenshtein bounds can be attained only by codes which are t...
详细信息
We consider spherical codes attaining the Levenshtein upper bounds on the cardinality of codes with prescribed maximal inner product. We prove that the even Levenshtein bounds can be attained only by codes which are tight spherical designs. For every fixed n greater than or equal to 5, there exist only a finite number of codes attaining the odd bounds. We derive different expressions for the distance distribution of a maximal code. As a by-product, we obtain a result about its inner products. We describe the parameters of those codes meeting the third Levenshtein bound, which have a regular simplex as a derived code. Finally, we discuss a connection between the maximal codes attaining the third bound and strongly regular graphs. (C) 1999 John Wiley & Sons, Inc.
The Plotkin bound and the quadratic bound for codes and (t, m, s)-nets can be obtained from the linear programming bound using certain linear and quadratic polynomials, respectively. We extend this approach by conside...
详细信息
The Plotkin bound and the quadratic bound for codes and (t, m, s)-nets can be obtained from the linear programming bound using certain linear and quadratic polynomials, respectively. We extend this approach by considering cubic and higher degree polynomials to find new explicit bounds as well as new non-existence results for codes and (t, m, s)-nets.
We study linear complementary pairs (LCP) of codes (C, D), where both codes belong to the same algebraic code family. We especially investigate constacyclic and quasicyclic LCP of codes. We obtain characterizations fo...
详细信息
We study linear complementary pairs (LCP) of codes (C, D), where both codes belong to the same algebraic code family. We especially investigate constacyclic and quasicyclic LCP of codes. We obtain characterizations for LCP of constacyclic codes and LCP of quasi-cyclic codes. Our result for the constacyclic complementary pairs extends the characterization of linear complementary dual (LCD) cyclic codes given by Yang and Massey. We observe that when C and I) are complementary and constacyclic, the codes C and D-perpendicular to are equivalent to each other. Hence, the security parameter min(d(C), d(D-perpendicular to)) for LCP of codes is simply determined by one of the codes in this case. The same holds for a special class of quasi-cyclic codes, namely 2D cyclic codes, but not in general for all quasi-cyclic codes, since we have examples of LCP of double circulant codes not satisfying this conclusion for the security parameter. We present examples of binary LCP of quasi-cyclic codes and obtain several codes with better parameters than known binary LCD codes. Finally, a linearprogramming hound is obtained for binary LCP of codes and a table of values from this bound is presented in the case d(C) = d(D-perpendicular to). This extends the linear programming bound for LCD codes.
暂无评论