Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SPARSE:
Reports tagged with sparse:
TR11-150 | 4th November 2011
Anna Gal, Kristoffer Arnsfelt Hansen, Michal Koucky, Pavel Pudlak, Emanuele Viola

#### 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) ... more >>>

ISSN 1433-8092 | Imprint