Generalized bicycle (GB) codes is a class of quantum errorcorrecting codes constructed from a pair of binary circulant matrices. Unlike for other simple quantum code ansätze, unrestricted GB codes may have linear distance scaling. In addition, lowdensity paritycheck GB codes have a naturally overcomplete set of lowweight stabilizer generators, which is expected to improve their performance in the presence of syndrome measurement errors. For such GB codes with a given maximum generator weight w, we constructed upper distance bounds by mapping them to codes local in D≤w−1 dimensions, and lower existence bounds which give d≥O(n1/2). We have also conducted an exhaustive enumeration of GB codes for certain prime circulant sizes in a family of twoqubit encoding codes with row weights 4, 6, and 8; the observed distance scaling is consistent with A(w)n1/2+B(w), where n is the code length and A(w) is increasing with w.
A Complete Linear Programming Hierarchy for Linear Codes
A longstanding open problem in coding theory is to determine the best (asymptotic) rate R₂(δ) of binary codes with minimum constant (relative) distance δ. An existential lower bound was given by Gilbert and Varshamov in the 1950s. On the impossibility side, in the 1970s McEliece, Rodemich, Rumsey and Welch (MRRW) proved an upper bound by analyzing Delsarte’s linear programs. To date these results remain the best known lower and upper bounds on R₂(δ) with no improvement even for the important class of linear codes. Asymptotically, these bounds differ by an exponential factor in the blocklength.
In this work, we introduce a new hierarchy of linear programs (LPs) that converges to the true size A^{Lin}₂(n,d) of an optimum linear binary code (in fact, over any finite field) of a given blocklength n and distance d. This hierarchy has several notable features:
1) It is a natural generalization of the Delsarte LPs used in the first MRRW bound.
2) It is a hierarchy of linear programs rather than semidefinite programs potentially making it more amenable to theoretical analysis.
3) It is complete in the sense that the optimum code size can be retrieved from level O(n²).
4) It provides an answer in the form of a hierarchy more »
 Editors:
 Braverman, Mark
 Award ID(s):
 1900460
 Publication Date:
 NSFPAR ID:
 10339897
 Journal Name:
 Leibniz international proceedings in informatics
 Volume:
 215
 Page Range or eLocationID:
 51:151:22
 ISSN:
 18688969
 Sponsoring Org:
 National Science Foundation
More Like this


The Gilbert–Varshamov bound nonconstructively establishes the existence of binary codes of distance 1/2−є/2 and rate Ω(є2). In a breakthrough result, TaShma [STOC 2017] constructed the first explicit family of nearly optimal binary codes with distance 1/2−є/2 and rate Ω(є2+α), where α → 0 as є → 0. Moreover, the codes in TaShma’s construction are єbalanced, where the distance between distinct codewords is not only bounded from below by 1/2−є/2, but also from above by 1/2+є/2. Polynomial time decoding algorithms for (a slight modification of) TaShma’s codes appeared in [FOCS 2020], and were based on the SumofSquares (SoS) semidefinite programming hierarchy. The running times for these algorithms were of the form NOα(1) for unique decoding, and NOє,α(1) for the setting of “gentle list decoding”, with large exponents of N even when α is a fixed constant. We derive new algorithms for both these tasks, running in time Õє(N). Our algorithms also apply to the general setting of decoding directsum codes. Our algorithms follow from new structural and algorithmic results for collections of ktuples (ordered hypergraphs) possessing a “structured expansion” property, which we call splittability. This property was previously identified and used in the analysis of SoSbased decoding and constraint satisfaction algorithms,more »

We study the classic set cover problem from the perspective of sublinear algorithms. Given access to a collection of m sets over n elements in the query model, we show that sublinear algorithms derived from existing techniques have almost tight query complexities. On one hand, first we show an adaptation of the streaming algorithm presented in [17] to the sublinear query model, that returns an αapproximate cover using Õ(m(n/k)^1/(α–1) + nk) queries to the input, where k denotes the value of a minimum set cover. We then complement this upper bound by proving that for lower values of k, the required number of queries is , even for estimating the optimal cover size. Moreover, we prove that even checking whether a given collection of sets covers all the elements would require Ω(nk) queries. These two lower bounds provide strong evidence that the upper bound is almost tight for certain values of the parameter k. On the other hand, we show that this bound is not optimal for larger values of the parameter k, as there exists a (1 + ε)approximation algorithm with Õ(mn/kε^2) queries. We show that this bound is essentially tight for sufficiently small constant ε, by establishing amore »

A collection of sets displays a proximity gap with respect to some property if for every set in the collection, either (i) all members are δclose to the property in relative Hamming distance or (ii) only a tiny fraction of members are δclose to the property. In particular, no set in the collection has roughly half of its members δclose to the property and the others δfar from it. We show that the collection of affine spaces displays a proximity gap with respect to ReedSolomon (RS) codes, even over small fields, of size polynomial in the dimension of the code, and the gap applies to any δ smaller than the Johnson/GuruswamiSudan listdecoding bound of the RS code. We also show nearoptimal gap results, over fields of (at least) linear size in the RS code dimension, for δ smaller than the unique decoding radius. Concretely, if δ is smaller than half the minimal distance of an RS code V ⊂ Fq n , every affine space is either entirely δclose to the code, or alternatively at most an ( n/q)fraction of it is δclose to the code. Finally, we discuss several applications of our proximity gap results to distributed storage, multipartymore »

Abstract—We study a problem of constructing codes that transform a channel with high bit error rate (BER) into one with low BER (at the expense of rate). Our focus is on obtaining codes with smooth (“graceful”) inputoutput BER curves (as opposed to thresholdlike curves typical for long errorcorrecting codes). This paper restricts attention to binary erasure channels (BEC) and contains two contributions. First, we introduce the notion of Low Density Majority Codes (LDMCs). These codes are nonlinear sparsegraph codes, which output majority function evaluated on randomly chosen small subsets of the data bits. This is similar to Low Density Generator Matrix codes (LDGMs), except that the XOR function is replaced with the majority. We show that even with a few iterations of belief propagation (BP) the attained inputoutput curves provably improve upon performance of any linear systematic code. The effect of nonlinearity bootstraping the initial iterations of BP, suggests that LDMCs should improve performance in various applications where LDGMs have been used traditionally. Second, we establish several twopoint converse bounds that lower bound the BER achievable at one erasure probability as a function of BER achieved at another one. The novel nature of our bounds is that they are specificmore »