Seminario Interdipartimentale di Algoritmica  

Monday, March 27, 2006, 12:00 noon
Derandomization: New Results and Applications
Emanuele Viola, Harvard University

DI - Department of Computer Science
Seminar Room, third floor

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 our results in 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. In a recent work, 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.