SPEAKER: Michal Koucky Mathematical Institute of Czech Academy of Sciences and University of Toronto
TITLE: Tight bounds on computing errorcorrecting codes by boundeddepth circuits with arbitrary gates
ABSTRACT:
In this talk I will present our recent results on computing errorcorrecting codes by boundeddepth circuits with arbitrary gates. We bound the minimum number w of wires needed to compute any (asymptotically good) errorcorrecting code C:{0,1}^Omega(n) > {0,1}^n with minimum distance Omega(n), using unbounded fanin 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 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).
We find the upper bounds surprising. They imply that a (necessarily dense) generator matrix for the code can be written as the product of two sparse matrices. The upper bounds are nonexplicit: we show the existence of circuits (consisting of only XOR gates) computing good codes within the stated bounds.
Using a result by Ishai, Kushilevitz, Ostrovsky, and Sahai (2008) we also obtain similar bounds for computing pairwiseindependent hash functions.
Furthermore, we identify a new class of superconcentratorlike graphs with connectivity properties distinct from previously studied ones.
This is joint work with A. Gal, K.A. Hansen, P. Pudlak and E. Viola.
