2023年05月31日 星期三

## 文章基本信息

• 标题：Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates
• 本地全文：下载
• 作者：
• 期刊名称：Electronic Colloquium on Computational Complexity
• 印刷版ISSN：1433-8092
• 出版年度：2011
• 卷号：2011
• 出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
• 摘要：

We bound the minimum number w of wires needed to compute any (asymptotically good) error-correcting codeC:01(n)01n with minimum distance (n),using unbounded fan-in circuits of depth d with arbitrary gates. Our main results are:

(1) If d=2 then w=(n(lognloglogn)2) .

(2) If d=3 then w=(nlglgn).

(3) If d=2k or d=2k+1 for some integer k2 then w=(nk(n)), where 1(n)=logn , i+1(n)=i(n), and the operation gives how many times one has to iterate the function i to reach a value at most 1 from the argument n.

(4) If d=logn then w=O(n).

Each bound is obtained for the first time in this paper.For depth d=2,our (n(lognloglogn)2) lower bound gives thelargest known lower bound for computing any linear map,improving on the (nlg32n) bound of Pudlak and Rodl (Discrete Mathematics '94).

We find the upper bounds surprising.They imply that a (necessarily dense) generator matrixfor the code can be written as the product of two sparse matrices.The upper bounds are non-explicit: we show the existence ofcircuits (consisting of only XOR gates) computing good codeswithin the stated bounds.

Using a result by Ishai, Kushilevitz, Ostrovsky, and Sahai (STOC '08),we also obtain similar bounds for computing pairwise-independent hashfunctions.

Furthermore, we identify a new class of superconcentrator-like graphs with connectivity properties distinct from previously-studied ones.

• 关键词：arbitrary gates; circuit depth; error-correcting code; lower bound; sparse; superconcentrator