Ph.D. Defense
The Complexity of Hardness Amplification and
Derandomization
Emanuele Viola, Harvard University
Place and Time: Monday 5/1, 11 AM. Maxwell Dworkin 119.
ABSTRACT
Randomness has proven to be a valuable resource
throughout computer science. In particular, there are several
fundamental computational problems that we know how to solve
efficiently only when we have a source of randomness at our
disposal. But to what extent is randomness really necessary for
efficient computation?
In this talk we survey some of the results in our Ph.D. thesis,
focusing on derandomization, which is the field that studies the
possibility and implications of simulating randomized
computation deterministically.
First, we address the derandomization of restricted
computational models, focusing on constant-depth circuits. We
develop a new application of the derandomization of
constant-depth circuits to the study of the average-case
complexity of NP. In particular, we show how to take any
function in NP that is `mildly' hard on average and transform it
into one that is `extremely' hard on average. We also obtain a
new sub-exponential time derandomization of constant-depth
circuits with few majority gates. This is currently the richest
randomized circuit class that researchers can simulate in
sub-exponential time.
We then discuss the derandomization of general computational
models. For general models, the only non-trivial derandomization
known is the '83 result that probabilistic polynomial time (BPP)
can be simulated in the second level of the polynomial-time
hierarchy. Perhaps surprisingly, in more than two decades no
work has addressed the running time of this simulation. We prove
that a quadratic slow-down in running time is inherent in this
simulation (for relativizing techniques). However, as our
results show, this quadratic slow-down disappears at the third
level of the polynomial-time hierarchy, and a quasilinear-time
simulation becomes possible.
No previous knowledge of complexity theory is required for this
talk.