Počet záznamů: 1
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates
- 1.
SYSNO ASEP 0386309 Druh ASEP C - Konferenční příspěvek (mezinárodní konf.) Zařazení RIV D - Článek ve sborníku Název Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates Tvůrce(i) Gál, A. (US)
Hansen, K.A. (DK)
Koucký, Michal (MU-W) RID, SAI, ORCID
Pudlák, Pavel (MU-W) RID, SAI
Viola, E. (US)Zdroj.dok. Proceedings of the 44th Symposium on Theory of Computing, STOC'2012. - New York : ACM, 2012 / Karloff H.J. ; Pitassi T. - ISBN 978-1-4503-1245-5 Rozsah stran s. 479-494 Poč.str. 26 s. Forma vydání Tištěná - P Akce STOC'12 Symposium on Theory of Computing Conference /44./ Datum konání 19.05.2012-22.05.2012 Místo konání New York Země US - Spojené státy americké Typ akce WRD Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova error correcting codes ; bounded depth circuits ; superconcentrators Vědní obor RIV BA - Obecná matematika CEP GBP202/12/G061 GA ČR - Grantová agentura ČR IAA100190902 GA AV ČR - Akademie věd 1M0545 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy Institucionální podpora MU-W - RVO:67985840 EID SCOPUS 84862625715 DOI 10.1145/2213977.2214023 Anotace We bound the minimum number w 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 d with arbitrary gates. Our main results are: (1) If d=2 then w = Theta(n (log n/ log log n)^2). (2) If d=3 then w = Theta(n log log n). (3) If d=2k or d=2k+1 for some integer k > 1 then w = Theta(n lambda_k(n)), where lambda_1(n)=log n, 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 $n$. (4) If d=log^* n then w=O(n). Each bound is obtained for the first time in our paper. For depth d=2, our Omega(n (log n/log log n)^2) lower bound gives the largest known lower bound for computing any linear map, improving on the Omega(n log^{3/2} n) bound of Pudlak and Rodl (1994). Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2013
Počet záznamů: 1