Conference
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates
| العنوان: | Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates |
|---|---|
| المؤلفون: | Gál, A., Hansen, K.A., Koucký, M. (Michal), Pudlák, P. (Pavel), Viola, E. |
| سنة النشر: | 2012 |
| المجموعة: | The Czech Academy of Sciences: Publication Activity (ASEP) / Akademie věd ČR - Publikační činnost |
| مصطلحات موضوعية: | error correcting codes, bounded depth circuits, superconcentrators |
| الوصف: | 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). |
| نوع الوثيقة: | conference object |
| اللغة: | English |
| ردمك: | 978-1-4503-1245-5 1-4503-1245-4 |
| Relation: | urn:isbn: 978-1-4503-1245-5; http://hdl.handle.net/11104/0219390 |
| DOI: | 10.1145/2213977.2214023 |
| الاتاحة: | https://doi.org/10.1145/2213977.2214023 http://hdl.handle.net/11104/0219390 |
| Rights: | info:eu-repo/semantics/restrictedAccess |
| رقم الانضمام: | edsbas.E104890D |
| قاعدة البيانات: | BASE |
| ردمك: | 9781450312455 1450312454 |
|---|---|
| DOI: | 10.1145/2213977.2214023 |