We study exact decoding for the toric code and for planar and rotated surface codes under the standard independent \(X/Z\) noise model, focusing on Separate Minimum Weight (SMW) decoding and Separate Most Likely Coset (SMLC) decoding. For the SMW decoding problem, we show that an \(O(n^{3/2}\log n)\)-time decoder is achievable for surface and toric codes, improving over the \(O(n^{3}\log n)\) worst-case time of the standard approach based on complete decoding graphs. Our approach is based on a local reduction of SMW decoding to the minimum weight perfect matching problem using Fisher gadgets, which preserves planarity for planar and rotated surface codes and genus~\(1\) for the toric code. This reduction enables the use of Lipton--Tarjan planar separator methods and implies that SMW decoding lies in \(\mathrm{NC}\). For SMLC decoding, we show that the planar surface code admits an exact decoder with \(O(n^{3/2})\) algebraic complexity and that the problem lies in \(\mathrm{NC}\), improving over the \(O(n^{2})\) algebraic complexity of Bravyi \emph{et al.} Our approach proceeds via a dual-cycle formulation of coset probabilities and an explicit reduction to planar Pfaffian evaluation using Fisher--Kasteleyn--Temperley constructions. The same complexity measures apply to SMLC decoding of the rotated surface code. For the toric code, we obtain an exact polynomial-time SMLC decoder with \(O(n^{3})\) algebraic complexity. In addition, while the SMLC formulation is motivated by connections to statistical mechanics, we provide a purely algebraic derivation of the underlying duality based on MacWilliams duality and Fourier analysis. Finally, we discuss extensions of the framework to the depolarizing noise model and identify resulting open problems.

Tietäväinen's upper and lower bounds assert that for block-length-n linear codes with dual distance d, the covering √ radius R is at most (n/2) - ((1/2) - o(1)) dn and typically at least (n/2) - θ((dn log (n/d))1/2). The gap between those bounds on R - (n/2) is a Θ((log (n/d))1/2) factor related to the gap between the worst covering radius given d and the sphere-covering bound. Our focus in this paper is on the case when d = o(n), i.e., when the code size is subexponential and the gap is w(1). We show that up to a constant, the gap can be eliminated by relaxing the covering requirement to allow for missing o(1) fraction of points. Namely, if the dual distance d = o(n), then for sufficiently large d, almost all points can be covered with radius R ≤ (n/2)-Θ((dn log (n/d))1/2). Compared with random linear codes, our bound on R - (n/2) is asymptotically tight up to a factor less than 3. We give applications to dual-BCH codes. The proof builds on the author's previous work on the weight distribution of cosets of linear codes, which we simplify in this paper and extend from codes to probability distributions on {0, 1}n, thus enabling the extension of the earlier result to (d - 1)-wise independent distributions.

We provide two corrections to the above-named work which do not affect the validity of any of the the reported results. First, we note that Conjecture 9 on page 6497 is not correct; a counter example follows from Cohen’s theorem[2]which asserts the existence of linear codes with covering radius up to the sphere-covering bound. The second correction is related to the “Proof of Theorem 2 using Theorem 5” on page 6496. In that proof, the$n$-point Discrete Fourier Transform (DFT) should be on$n+1$points. The other steps of the proof hold without modification. We reproduce below the corrected proof with the needed modifications in bold. The issue with the$n$-point DFT is that it makes Identity(1)below incorrect for$b=n$.

The bilateral minimum distance of a binary linear code is the maximum d such that all nonzero codewords have weights between d and n - d. Let Q ⊂ {0,1}nbe a binary linear code whose dual has bilateral minimum distance at least d, where d is odd. Roughly speaking, we show that the average L∞-distance-and consequently, the L1-distance-between the weight distribution of a random cosets of Q and the binomial distribution decays quickly as the bilateral minimum distance d of the dual of Q increases. For d = ⊖(1), it decays like n-⊖(d). On the other d = ⊖(n) extreme, it decays like and e-⊖(d). It follows that, almost all cosets of Q have weight distributions very close to the to the binomial distribution. In particular, we establish the following bounds. If the dual of Q has bilateral minimum distance at least d = 2t + 1, where t ≥ 1 is an integer, then the average L∞-distance is at most min{(e ln (n/2t))t(2t/n)(t/2), √2e-(t/10)}. For the average L1-distance, we conclude the bound min{(2t + 1)(e ln (n/2t))t(2t/n)(t/2)-1, √2(n + 1)e-(t/10)}, which gives nontrivial results for t ≥ 3. We give applications to the weight distribution of cosets of extended Hadamard codes and extended dual BCH codes. Our argument is based on Fourier analysis, linear programming, and polynomial approximation techniques.

Feldman et al. [1] asked whether the performance of the Linear Programming (LP) decoder can be improved by adding redundant parity checks to tighten the LP relaxation. We prove in this paper that for LDPC codes, even if we include all redundant parity checks, asymptotically there is no gain in the LP decoder threshold on the Binary Symmetric Channel (BSC) under certain conditions on the base Tanner graph. First, we show that if the base Tanner graph has bounded check-degree and satisfies a condition which we call asymptotic strength, then including high degree redundant parity checks in the LP does not significantly improve the threshold of the LP decoder in the following sense: for each constant δ > 0, there is a constant k > 0 such that the threshold of the LP decoder containing all redundant checks of degree at most k improves by at most δ upon adding to the LP all redundant checks of degree larger than k. We conclude that if the graph satisfies an additional condition which we call rigidity, then including all redundant checks does not improve the threshold of the base LP. We call the graph asymptotically strong if the LP decoder corrects a constant fraction of errors even if the log-likelihood-ratios of the correct variables are arbitrarily small. By building on a construction due Feldman et al. [2] and its recent improvement by Viderman [3], we show that asymptotic strength follows from sufficiently large variable-to-check expansion. We also give a geometric interpretation of asymptotic strength in terms pseudocodewords. We call the graph rigid if the minimum weight of a sum of check nodes involving a cycle tends to infinity as the block length tends to infinity. Under the assumptions that the graph girth is logarithmic and the minimum check degree is at least 3, rigidity is equivalent to the nondegeneracy property that adding at least logarithmically many checks does not give a constant weight check. We argue that nondegeneracy is a typical property of random check-regular Tanner graphs.

Feldman et al. [11] asked whether the performance of the linear programming (LP) decoder can be improved by adding redundant parity checks to tighten the LP relaxation. We prove in this paper that for low-density parity-check codes, even if we include all redundant parity checks, asymptotically there is no gain in the LP decoder threshold on the binary symmetric channel under certain conditions on the base Tanner graph. First, we show that if the Tanner graph has bounded check-degree and satisfies a condition which we call asymptotic strength, then including high degree redundant parity checks in the LP does not significantly improve the threshold of the LP decoder in the following sense. For each constant δ > 0, there is a constant k > 0 such that the threshold of the LP decoder containing all redundant checks of degree at most k improves by at most δ upon adding to the LP all redundant checks of degree larger thank. We conclude that if the graph satisfies an additional condition which we call rigidity, then including all redundant checks does not improve the threshold of the base LP. We call the graph asymptotically strong if the LP decoder corrects a constant fraction of errors even if the log-likelihood-ratios of the correct variables are arbitrarily small. By building on a construction due Feldman et al. [9] and its recent improvement by Viderman [24], we show that asymptotic strength follows from sufficiently large variable-to-check expansion. We also give a geometric interpretation of asymptotic strength in terms pseudocodewords. We call the graph rigid if the minimum weight of a sum of check nodes involving a cycle tends to infinity as the block length tends to infinity. Under the assumptions that the graph girth is logarithmic and the minimum check degree is at least 3, rigidity is equivalent to the nondegeneracy property that adding at least logarithmically many checks does not give a constant weight check. We argue that nondegeneracy is a typical property of random check-regular Tanner graphs.

For a given family of spatially coupled codes, we prove that the linear programming (LP) threshold on the binary-symmetric channel (BSC) of the tail-biting graph cover ensemble is the same as the LP threshold on the BSC of the derived spatially coupled ensemble. This result is in contrast with the fact that spatial coupling significantly increases the belief propagation threshold. To prove this, we establish some properties related to the dual witness for LP decoding. More precisely, we prove that the existence of a dual witness, which was previously known to be sufficient for LP decoding success, is also necessary and is equivalent to the existence of certain acyclic hyperflows. We also derive a sublinear (in the block length) upper bound on the weight of any edge in such hyperflows, both for regular low-density parity-check (LPDC) codes and spatially coupled codes and we prove that the bound is asymptotically tight for regular LDPC codes. Moreover, we show how to trade crossover probability for LP excess on all the variable nodes, for any binary linear code.

For a given family of spatially coupled codes, we prove that the LP threshold on the BSC of the tail-biting graph cover ensemble is the same as the LP threshold on the BSC of the derived spatially coupled ensemble. This result is in contrast with the fact that the BP threshold of the derived spatially coupled ensemble is believed to be larger than the BP threshold of the tail-biting graph cover ensemble [1], [2].

We show that any k-wise independent probability distribution on $\{0,1\}^n$ $O(m^{2.2}$ $2^{-\sqrt{k}/10})$-fools any boolean function computable by an m-clause disjunctive normal form (DNF) (or conjunctive normal form (CNF)) formula on n variables. Thus, for each constant $e>0$, there is a constant $c>0$ such that any boolean function computable by an m-clause DNF (or CNF) formula is $m^{-e}$-fooled by any $c\log^2m$-wise probability distribution. This resolves up to an $O(\log m)$ factor the depth-2 circuit case of a conjecture due to Linial and Nisan [Combinatorica, 10 (1990), pp. 349–365]. The result is equivalent to a new characterization of DNF (or CNF) formulas by low degree polynomials. It implies a similar statement for probability distributions with the small bias property. Using known explicit constructions of small probability spaces having the limited independence property or the small bias property, we directly obtain a large class of explicit pseudorandom generators of $O(\log^2m\log n)$-seed length for m-clause DNF (or CNF) formulas on n variables, improving previously known seed lengths.

Worst-case upper bounds are derived on the minimum distance of parallel concatenated turbo codes, serially concatenated convolutional codes, repeat-accumulate codes, repeat-convolute codes, and generalizations of these codes obtained by allowing nonlinear and large-memory constituent codes. It is shown that parallel-concatenated turbo codes and repeat-convolute codes with sub-linear memory are asymptotically bad. It is also shown that depth-two serially concatenated codes with constant-memory outer codes and sublinear-memory inner codes are asymptotically bad. Most of these upper bounds hold even when the convolutional encoders are replaced by general finite-state automata encoders. In contrast, it is proven that depth-three serially concatenated codes obtained by concatenating a repetition code with two accumulator codes through random permutations can be asymptotically good.

We show that any k-wise independent probability measure on {0, 1}ncan O(m2ldr2ldr2-radick/10)-fool any boolean function computable by an rn-clauses DNF (or CNF) formula on n variables. Thus, for each constant c > 0. there is a constant e > 0 such that any boolean function computable by an m-clauses DNF (or CNF) formula can be in m-e-fooled by any clog in-wise probability measure. This resolves, asymptotically and up to a logm factor, the depth-2 circuits case of a conjecture due to Linial and Nisan (1990). The result is equivalent to a new characterization of DNF (or CNF) formulas by low degree polynomials. It implies a similar statement for probability measures with the small bias property. Using known explicit constructions of small probability spaces having the limited independence property or the small bias property, we. directly obtain a large class of explicit PRG's ofO(log2m log n)-seed length for m-clauses DNF (or CNF) formulas on n variables, improving previously known seed lengths.

A bound on the minimum distance of a binary error-correcting code is established given constraints on the computational time-space complexity of its encoder where the encoder is modeled as a branching program. The bound obtained asserts that if the encoder uses linear time and sublinear memory in the most general sense, then the minimum distance of the code cannot grow linearly with the block length when the rate is nonvanishing, that is, the minimum relative distance of the code tends to zero in such a setting. The setting is general enough to include nonserially concatenated turbo-like codes and various generalizations. Our argument is based on branching program techniques introduced by Ajtai. The case of constant-depth AND-OR circuit encoders with unbounded fanins are also considered.

We show that for the case of the binary-symmetric channel and Gallager's decoding algorithm A the threshold can, in many cases, be determined analytically. More precisely, we show that the threshold is always upper-bounded by the minimum of (1-/spl lambda//sub 2//spl rho/'(1))/(/spl lambda/'(1)/spl rho/'(1)-/spl lambda//sub 2//spl rho/'(1)) and the smallest positive real root /spl tau/ of a specific polynomial p(x) and we observe that for most cases this bound is tight, i.e., it determines the threshold exactly. We also present optimal degree distributions for a large range of rates. In the case of rate one-half codes, for example, the threshold x/sub 0//sup */ of the optimal degree distribution is given by x/sup *//sub 0//spl sim/0.0513663. Finally, we outline how thresholds of more complicated decoders might be determined analytically.

The problem of matching two planar sets of points in the presence of geometric uncertainty has important applications in pattern recognition, image understanding, and robotics. The first set of points corresponds to the "template." The other set corresponds to the "image" that-possibly-contains one or more deformed versions of the "template" embedded in a cluttered image. Significant progress has been made on this problem and various polynomial-time algorithms have been proposed. We show how to sample the "image" in linear time, reducing the number of foreground points n by a factor of two-six (for commonly occurring images) without degrading the quality of the matching results. The direct consequence is a time-saving by a factor of 2/sup p/-6/sup p/ for an O(n/sup p/) matching algorithm. Our result applies to a fairly large class of available matching algorithms.