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

  • 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 languageEnglish
Title of host publicationSTOC '12 Proceedings of the 44th symposium on Theory of Computing
EditorsHoward Karloff, Toniann Pitassi
Number of pages15
PublisherAssociation for Computing Machinery
Publication year2012
Pages479-494
ISBN (print)978-1-4503-1245-5
DOIs
Publication statusPublished - 2012
EventSymposium on Theory og Computing - SanJosé, United States
Duration: 6 Jun 20128 Jun 2012
Conference number: 44

Conference

ConferenceSymposium on Theory og Computing
Nummer44
LandUnited States
BySanJosé
Periode06/06/201208/06/2012

See relations at Aarhus University Citationformats

ID: 51836099