Number of the records: 1
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates
- 1.
SYSNO ASEP 0422134 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates Author(s) Gál, A. (US)
Hansen, A. K. (DK)
Koucký, Michal (MU-W) RID, SAI, ORCID
Pudlák, Pavel (MU-W) RID, SAI
Viola, E. (US)Source Title IEEE Transactions on Information Theory. - : Institute of Electrical and Electronics Engineers - ISSN 0018-9448
Roč. 59, č. 10 (2013), s. 6611-6627Number of pages 17 s. Language eng - English Country US - United States Keywords bounded-depth circuits ; error-correcting codes ; hashing Subject RIV BA - General Mathematics R&D Projects IAA100190902 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR) Institutional support MU-W - RVO:67985840 UT WOS 000324573500028 EID SCOPUS 84884402189 DOI 10.1109/TIT.2013.2270275 Annotation 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. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2014
Number of the records: 1