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

0422134 - MÚ 2014 RIV US eng J - Journal Article
Gál, A. - Hansen, A. K. - Koucký, Michal - Pudlák, Pavel - Viola, E.
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates.
IEEE Transactions on Information Theory. Roč. 59, č. 10 (2013), s. 6611-6627. ISSN 0018-9448. E-ISSN 1557-9654
R&D Projects: GA AV ČR IAA100190902
Institutional support: RVO:67985840
Keywords : bounded-depth circuits * error-correcting codes * hashing
Subject RIV: BA - General Mathematics
Impact factor: 2.650, year: 2013
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6578188

We bound the minimum number of wires needed to compute any (asymptotically good) error-correcting code C : {0, 1}(Omega(n)) -> {0, 1}(n) with minimum distance Omega(n), using unbounded fan-in circuits of depth with arbitrary gates. Our main results are: 1) if d = 2, then w = Theta(n(lg n/lg lg n)(2)); 2) if d = 3, then w = Theta(n lg lg n); 3) if d = 2k or d = 2k + 1 for some integer k >= 2, then w = Theta(n lambda(k)(n)), where lambda(1)(n) = inverted rightlg ninverted left perpendicular lambda(i+1)(n) = lambda(i)*(n), and the * operation gives how many times one has to iterate the function lambda(i) to reach a value at most 1 from the argument; and 4) if d = lg* n, then w = O(n). For depth d = 2, our Omega(n(lg n/lg lg n)(2)) 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.
Permanent Link: http://hdl.handle.net/11104/0228346