## Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

### DOI

• Anna Gál , University of Texas at Austin, Austin, TX, , United States
• Kristoffer Arnsfelt Hansen
• Michal Koucký, Institute of Mathematics, the Academy of Sciences of the CzechRrepublic, United States
• Pavel Pudlák, Institute of Mathematics, the Academy of Sciences of the CzechRrepublic, United States
• Emanuele Viola, Northeastern University, Boston, United States

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

For depth d=2, our Ω(n (log n/log log n)2) lower bound gives the largest known lower bound for computing any linear map.

Using a result by Ishai, Kushilevitz, Ostrovsky, and Sahai (2008), we also obtain similar 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.
Original language English STOC '12 Proceedings of the 44th symposium on Theory of Computing Howard Karloff, Toniann Pitassi 15 Association for Computing Machinery 2012 479-494 978-1-4503-1245-5 https://doi.org/10.1145/2213977.2214023 Published - 2012 Symposium on Theory og Computing - SanJosé, United StatesDuration: 6 Jun 2012 → 8 Jun 2012Conference number: 44

### Conference

Conference Symposium on Theory og Computing 44 United States SanJosé 06/06/2012 → 08/06/2012

Citationformats