Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-150 | 4th November 2011 21:03

Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates



We bound the minimum number $w$ of wires needed to compute any (asymptotically good) error-correcting code
$C:\{0,1\}^{\Omega(n)} \to \{0,1\}^n$ with minimum distance $\Omega(n)$,
using unbounded fan-in circuits of depth $d$ with arbitrary gates. Our main results are:

(1) If $d=2$ then $w = \Theta(n ({\log n/ \log \log n})^2)$.

(2) If $d=3$ then $w = \Theta(n \lg \lg n)$.

(3) If $d=2k$ or $d=2k+1$ for some integer $k\ge 2$ then $w = \Theta(n \lambda_k(n))$, where $\lambda_1(n)=\lceil \log n\rceil$, $\lambda_{i+1}(n)=\lceil \lambda_i^*(n)\rceil$, and the $*$ operation gives how many times one has to iterate the function $\lambda_i$ to reach a value at most 1 from the argument $n$.

(4) If $d=\log^* n$ then $w=O(n)$.

Each bound is obtained for the first time in this paper.
For depth $d=2$,
our $\Omega(n ({\log n/\log \log n})^2)$ lower bound gives the
largest known lower bound for computing any linear map,
improving on the $\Omega(n \lg^{3/2} n)$ bound of Pudlak and Rodl (Discrete Mathematics '94).

We find the upper bounds surprising.
They imply that a (necessarily dense) generator matrix
for the code can be written as the product of two sparse matrices.
The upper bounds are non-explicit: we show the existence of
circuits (consisting of only XOR gates) computing good codes
within the stated bounds.

Using a result by Ishai, Kushilevitz, Ostrovsky, and Sahai (STOC '08),
we also obtain similar bounds for computing pairwise-independent hash

Furthermore, we identify a new class of superconcentrator-like graphs with connectivity properties distinct from previously-studied ones.

ISSN 1433-8092 | Imprint