**You are here:**
» Tight bounds on computing error-correcting codes by bound...

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

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-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 language | English |
---|

Title of host publication | STOC '12 Proceedings of the 44th symposium on Theory of Computing |
---|

Editors | Howard Karloff, Toniann Pitassi |
---|

Number of pages | 15 |
---|

Publisher | Association for Computing Machinery |
---|

Publication year | 2012 |
---|

Pages | 479-494 |
---|

ISBN (print) | 978-1-4503-1245-5 |
---|

DOIs | |
---|

Publication status | Published - 2012 |
---|

Event | Symposium on Theory og Computing - SanJosé, United States Duration: 6 Jun 2012 → 8 Jun 2012 Conference number: 44 |
---|

Conference | Symposium on Theory og Computing |
---|

Nummer | 44 |
---|

Land | United States |
---|

By | SanJosé |
---|

Periode | 06/06/2012 → 08/06/2012 |
---|

See relations at Aarhus University
Citationformats

ID: 51836099