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

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • A. Gal, University of Texas at Austin, Dept. of Comput. Sci, United States
  • Kristoffer Arnsfelt Hansen
  • Michal Koucky, Denmark
  • P. Pudlak, Academy of Sciences
  • ,
  • E. Viola, Northeastern University, University of Texas at Austin
We bound the minimum number w of wires needed to compute any (asymptotically good) error-correcting code C:{0,1}Ω (n) to {0,1} 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({lg n/lg lgn));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)=\lceil\lg n\rceil, λi+1(n)= λi*(n) , and the \ast operation gives how many times one has to iterate the function λ to reach a value at most 1 from the argument n; and 4) if d=lg*n , then w=O(n). For depth d=2 , our Ω (n (lg n/lglgn) ) 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.
Original languageEnglish
JournalI E E E Transactions on Information Theory
Volume59
Issue10
Pages (from-to)6611-6627
Number of pages17
ISSN0018-9448
DOIs
Publication statusPublished - 1 Jan 2013

See relations at Aarhus University Citationformats

ID: 62052970