ECCC-Report TR11-150https://eccc.weizmann.ac.il/report/2011/150Comments and Revisions published for TR11-150en-usFri, 04 Nov 2011 21:03:57 +0200
Paper TR11-150
| Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates |
Emanuele Viola,
Michal Koucky,
Anna Gal,
Pavel Pudlak,
Kristoffer Arnsfelt Hansen
https://eccc.weizmann.ac.il/report/2011/150We 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.
Fri, 04 Nov 2011 21:03:57 +0200https://eccc.weizmann.ac.il/report/2011/150