DIMACS Theoretical Computer Science Seminar

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


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.

See: http://paul.rutgers.edu/~yixinxu/theory-fall12.html