Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates

We bound the minimum numberwof wires needed to compute any (asymptotically good) error-correcting codeC:\0,1\Ω (n)→\0,1\ⁿwith minimum distanceΩ (n), using unbounded fan-in circuits of depthdwith arbitrary gates. Our main results are: 1) if$d=2$, thenw=Θ (n ( n/ n)²); 2) if$d=3$, thenw=Θ (n n); 3) if$d=2k$or$d=2k+1$for some integerk≥ 2, thenw=Θ (nλₖ(n)), whereλ₁(n)= n,λᵢ₊₁(n)=λᵢ^(n), and theoperation gives how many times one has to iterate the functionλᵢto reach a value at most 1 from the argumentn; and 4) ifd=^n, then$w=O(n)$. For depth$d=2$, ourΩ (n ( n/ n)²)lower bound gives the largest known lower bound for computing any linear map. The upper bounds imply that a (necessarily dense) generator matrix for our code can be written as the product of two sparse matrices. Using known techniques, we also obtain similar (but not tight) bounds for computing pairwise-independent hash functions. Our lower bounds are based on a superconcentrator-like condition that the graphs of circuits computing good codes must satisfy. This condition is provably intermediate between superconcentrators and their weakenings considered before.