TR11-150 Authors: Anna Gal, Kristoffer Arnsfelt Hansen, Michal Koucky, Pavel Pudlak, Emanuele Viola

Publication: 4th November 2011 21:03

Downloads: 2281

Keywords:

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

functions.

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