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

0386309 - MÚ 2013 RIV US eng C - Konferenční příspěvek (zahraniční konf.)
Gál, A. - Hansen, K.A. - Koucký, Michal - Pudlák, Pavel - Viola, E.
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates.
Proceedings of the 44th Symposium on Theory of Computing, STOC'2012. New York: ACM, 2012 - (Karloff, H.; Pitassi, T.), s. 479-494. ISBN 978-1-4503-1245-5.
[STOC'12 Symposium on Theory of Computing Conference /44./. New York (US), 19.05.2012-22.05.2012]
Grant CEP: GA ČR GBP202/12/G061; GA AV ČR IAA100190902; GA MŠMT(CZ) 1M0545
Institucionální podpora: RVO:67985840
Klíčová slova: error correcting codes * bounded depth circuits * superconcentrators
Kód oboru RIV: BA - Obecná matematika
http://dl.acm.org/citation.cfm?id=2213977.2214023&coll=DL&dl=GUIDE&CFID=245194486&CFTOKEN=14126751

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).
Trvalý link: http://hdl.handle.net/11104/0219390