Algorithms and Complexity Seminar
Thursday, February 16, 2006, 4-5:15pm in 32-G575.
New constructions of epsilon-biased generators.
Amir Shpilka (Technion)
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.
Host: Madhu Sudan