The Derandomization Study Group

Yesterday we started the derandomization study group. Thanks to Srikanth for starting this group. We will meet every Saturday and study the field. The members are Srikanth, Nutan, Somnath, Raghu, Partha and myself. Srikanth gave a nice introduction of the field. The following is roughly what he talked about:

Disclaimer: the summaries below are from my notes and may not be
exactly what Srikanth told or may not be 100% accurate, and would
welcome corrections.

Derandomization is a subfield of theoretical computer science whose
main goal is reducing randomness (possibly to zero) from randomized
algorithms. If we want to reduce the amount of randomness we might
have to sacrifice some other resource like time or
space. The goal of `derandomizing time’ is to reduce randomness used
by the algorithm without increasing the time too much. Similarly, The
goal of `derandomizing space’ is to reduce randomness by the algorithm
without significantly increasing the space used by the algorithm. The
‘holy grail’ derandomizing time would be the question, where
one asks if we can remove the randomness altogether form algorithms
that solves a problem in polynomial time and uses polynomially many
random bits. I feel that settling this question will not only be a
great achievement in computer science but also a great philosophical
achievement. But very little progress has been done in this
direction. We do not have any unconditional good result. But lots of
progress has been made in the case of derandomizing space. The recent
result by Omer Riengold is a big stride in this direction. While
or questions seems hard nut to crack a less
ambitious goal would be to reduce the error probability without taking
much extra bit of randomness or to use weak random sources.

The different important combinatorial tools for understanding this field are

1) Expanders
2) Extractors
3) Pseudorandom generators and
4) Codes

Srikanth mentioned some results in the direction of error
amplification, weak random sources, derandomization of space and
derandomization of time. We will be covering all of these
results. Here I will mention only two of them

1) Suppose an algorithm runs in time and uses r random bits,
and gives the correct answer with probability . We want
to improve the error probability. The naive approach is to repeat
the algorithm times and get error probability less than
. But Impagliazzo and Zuckerman showed that we can do
much better. We can use only random bits and still have
error probability less than .

2) Impagliazzo and Wigderson’s result: unless has
subexponential circuits. is the class of problems that can be
solved in polynomial time. is the class of problems which can
be solved by algorithms that takes polynomial time and uses
polynomially many random bits. . We don’t know
whether there is any language L in E that cannot be computed with
a circuit of size . But there certainly
might be some language. In that case .

Advertisements

~ by bireswar on May 12, 2007.