CSAIL Event Calendar: Previous Series

New constructions of epsilon-biased generators

Speaker: Amir Shpilka , Technion
Date: February 16 2006
Time: 4:00PM to 5:15AM
Location: 32-G575
Host: Madhu Sudan, MIT CSAIL

An epsilon-biased generator is a mapping from m bits to n bits such that the output distribution is unbiased with respect to linear tests (or in other words, every hyperspace contains roughly half of the output). In this talk we give three constructions of epsilon-biased generators. The first construction gives an epsilon-biased generator in NC0, i.e. every output bit of the generator depends only on a constant number of input bits. Our second construction gives a generator in which every output bit is a low degree polynomial and whose output length (i.e. n) is nearly optimal. Our third construction yields a generator whose image is a good error correcting code that has efficient encoding and decoding algorithms.

The motivation from studying epsilon-biased generators follows from their many applications in different areas of computer science including derandomization, inapproximability results, learning theory, construction of efficient low degree tests and short PCPs, and construction of two-source extractors. The specific questions that we study are very natural: Constructions in NC0 are extremely efficient and it is thus interesting to find which objects can be constructed there, in particular the question of constructing epsilon-biased generators in NC0 was raised (and left open) by Cryan and Miltersen in '01. Low degree polynomials are also a natural "low complexity" class and it is interesting to find how good can low degree generators be. This question was first studied in a joint work with Mossel and Trevisan where only the case of degree 2 was solved. Finally, the usefulness of epsilon-biased generators and of error correcting codes raises the natural question of trying to achieve a construction that is both a good code and an epsilon-biased generator. The question of constructing such generators was asked and left open by Dodis and Smith in '05.

Part of this talk is based on a joint work with Elchanan Mossel and Luca Trevisan.

See other events that are part of Algorithms and Complexity Spring 2006

See other events happening in February 2006