Journal
IEEE TRANSACTIONS ON INFORMATION THEORY
Volume 59, Issue 10, Pages 6611-6627Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2013.2270275
Keywords
Bounded-depth circuits; error-correcting codes; hashing; lower bounds; superconcentrators
Funding
- Division of Computing and Communication Foundations
- Direct For Computer & Info Scie & Enginr [1018060] Funding Source: National Science Foundation
Ask authors/readers for more resources
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. 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available