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} Ω(n) -> {0,1} n with minimum distance Ω(n), using unbounded fan-in circuits of depth d with arbitrary gates. Our main results are: (1) If d=2 then w = Θ(n ({log n/ log log n}) 2 ). (2) If d=3 then w = Θ(n lg lg n). (3) If d=2k or d=2k+1 for some integer k ≥ 2 then w = Θ(n λ k (n)), where λ 1 (n)=⌈ log n⌉, λ i+1 (n)= λ i *(n), and the * operation gives how many times one has to iterate the function λ i to reach a value at most 1 from the argument n. (4) If d=log* n then w=O(n).

Authors

• Anna Gál
• Kristoffer Arnsfelt Hansen
• Michal Koucký 0001
• Pavel Pudlák
• Emanuele Viola

Keywords

• bounded-depth circuits
• error-correcting codes
• hashing
• lower bounds
• superconcentrators