We deal with connected k-regular multigraphs of order n that has only three distinct eigenvalues. In this paper, we study the largest possible number of vertices of such a graph for given k. For k = 2, 3, 7, the Moore...
详细信息
We deal with connected k-regular multigraphs of order n that has only three distinct eigenvalues. In this paper, we study the largest possible number of vertices of such a graph for given k. For k = 2, 3, 7, the Moore graphs are largest. For k not similar or equal to 2, 3, 7, 57, we show an upper bound n <= k(2)- k + 1, with equality if and only if there exists a finite projective plane of order k -1 that admits a polarity. (C) 2019 Elsevier B.V. All rights reserved.
It is possible to view communication complexity as the minimum solution of an integer programming problem. This integer programming problem is relaxed to a linearprogramming problem and from it information regarding ...
详细信息
It is possible to view communication complexity as the minimum solution of an integer programming problem. This integer programming problem is relaxed to a linearprogramming problem and from it information regarding the original communication complexity question is deduced. A particularly appealing avenue this opens is the possibility of proving lower bounds on the communication complexity (which is a minimization problem) by exhibiting upper bounds on the maximization problem defined by the dual of the linear program. This approach works very neatly in the case of nondeterministic communication complexity. In this case a special case of Lovasz's fractional cover measure is obtained. Through it the amortized nondeterministic communication complexity is completely characterized. The power of the approach is also illustrated by proving lower and upper bounds on the nondeterministic communication complexity of various functions. In the case of deterministic complexity the situation is more complicated. Two attempts are discussed and some results using each of them are obtaied. The main result regarding the first attempt is negative: one cannot use this method for proving superpolynomial lower bounds for formula size. The main result regarding the second attempt is a ''direct-sum'' theorem for two-round communication complexity.
The dual of an entanglement-assisted quantum error-correcting (EAQEC) code is defined from the orthogonal group of a simplified stabilizer group. From the Poisson summation formula, this duality leads to the MacWillia...
详细信息
The dual of an entanglement-assisted quantum error-correcting (EAQEC) code is defined from the orthogonal group of a simplified stabilizer group. From the Poisson summation formula, this duality leads to the MacWilliams identities and linear programming bounds for EAQEC codes. We establish a table of upper and lower bounds on the minimum distance of any maximal-entanglement EAQEC code with length up to 15 channel qubits.
作者：
Yu, LeiNankai Univ
Sch Stat & Data Sci LPMC Tianjin 300071 Peoples R China Nankai Univ
KLMDASR Tianjin 300071 Peoples R China
Let Q(n)(r) be the graph with vertex set { -1, 1}(n) in which two vertices are joined if their Hamming distance is at most r. The edge-isoperimetric problem for Q(n)(r) is that: For every (n, r, M) such that 1 infini...
详细信息
Let Q(n)(r) be the graph with vertex set { -1, 1}(n) in which two vertices are joined if their Hamming distance is at most r. The edge-isoperimetric problem for Q(n)(r) is that: For every (n, r, M) such that 1 <= r <= n and 1 <= M <= 2(n), determine the minimum edge-boundary size of a subset of vertices of Q(n)(r) with a given size M. In this paper, we apply two different approaches to prove bounds for this problem. The first approach is a linearprogramming approach and the second is probabilistic. Our bound derived by the first approach generalizes the tight bound for M = 2(n-1) derived by Kahn, Kalai, and Linial in 1989. Moreover, our bound is also tight for M = 2(n-2) and r <= n/2- 1. Our bounds derived by the second approach are expressed in terms of the noise stability, and they are shown to be asymptotically tight as n -> infinity when r = 2 left perpendicular beta n/2right perpendicular + 1 and M = left perpendicular alpha 2(n)right perpendicular for fixed alpha, beta is an element of (0,1), and is tight up to a factor 2 when r = 2left perpendicular beta n/2right perpendicular and M = left perpendicular alpha 2(n)right perpendicular. In fact, the edge-isoperimetric problem is equivalent to a ball-noise stability problem which is a variant of the traditional (i.i.d.-) noise stability problem. Our results can be interpreted as bounds for the ball-noise stability problem. (C) 2021 Elsevier Inc. All rights reserved.
A lambda-fold r-packing in a Hamming metric space is a code C such that the radius-r balls centered in C cover each vertex of the space by not more than lambda-times. The well-known r-error-correcting codes correspond...
详细信息
ISBN:
(纸本)9781538692912
A lambda-fold r-packing in a Hamming metric space is a code C such that the radius-r balls centered in C cover each vertex of the space by not more than lambda-times. The well-known r-error-correcting codes correspond to the case lambda = 1. We propose asymptotic bounds for q-ary 2-fold 1-packings as q grows, find that the maximum size of a binary 2-fold 1-packing of length 9 is 96, and derive upper bounds for the size of a binary lambda-fold 1-packing.
Special matrices are explored in many areas of science and technology. Krawtchouk matrix is such a matrix that plays important role in coding theory and theory of orthogonal arrays also called fractional factorial des...
详细信息
ISBN:
(纸本)9783030410322;9783030410315
Special matrices are explored in many areas of science and technology. Krawtchouk matrix is such a matrix that plays important role in coding theory and theory of orthogonal arrays also called fractional factorial designs in planning of experiments and statistics. In this paper we give explicitly Smith normal forms of Krawtchouk matrix and its extended matrix. Also we propose a computationally effective method for determining the Hamming distance distributions of an orthogonal array with given parameters. The obtained results facilitate the solving of many existence and classification problems in theory of codes and orthogonal arrays.
We derive upper and lower bounds on the sum of distances of a spherical code of size N in n dimensions when N = O(n alpha), 0 < alpha 2. The bounds are derived by specializing recent general, universal bounds on en...
详细信息
We derive upper and lower bounds on the sum of distances of a spherical code of size N in n dimensions when N = O(n alpha), 0 < alpha 2. The bounds are derived by specializing recent general, universal bounds on energy of spherical sets. We discuss asymptotic behavior of our bounds along with several examples of codes whose sum of distances closely follows the upper bound.(c) 2023 Elsevier B.V. All rights reserved.
暂无评论