### 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

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.

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