Počet záznamů: 1
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates
- 1.
SYSNO ASEP 0422134 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates Tvůrce(i) 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)Zdroj.dok. IEEE Transactions on Information Theory. - : Institute of Electrical and Electronics Engineers - ISSN 0018-9448
Roč. 59, č. 10 (2013), s. 6611-6627Poč.str. 17 s. Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova bounded-depth circuits ; error-correcting codes ; hashing Vědní obor RIV BA - Obecná matematika CEP IAA100190902 GA AV ČR - Akademie věd Institucionální podpora MU-W - RVO:67985840 UT WOS 000324573500028 EID SCOPUS 84884402189 DOI 10.1109/TIT.2013.2270275 Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2014
Počet záznamů: 1