Title: Computing error-correcting codes by bounded-depth circuits
Speaker: Michal Koucky, Czech Academy of Sciences in Prague
Date: Wednesday, November 14, 2012 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 301A, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
In this talk I will present our recent results on computing error- correcting codes by bounded-depth circuits with arbitrary gates. We study 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. We show nearly linear upper bounds as well as matching lower bounds.
To prove our lower bounds we exhibit a connection between circuits computing the error-correcting codes and a new class of superconcentrator-like graphs with connectivity properties distinct from previously studied ones.
Our upper bounds imply that a (necessarily dense) generator matrix for the code can be written as the product of two sparse matrices. The upper bounds are non-explicit: 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 pairwise-independent hash functions.
Joint work with A. Gal, K.A. Hansen, P. Pudlak and E. Viola.