Abstract
The program of unconditionally constructing pseudorandom generators (PRGs) and of unconditionally derandomizing probabilistic algorithms had two early breakthroughs: Nisan's PRG for space-bounded algorithms and the Nisan-Wigderson PRG for bounded-depth circuits.
Twenty years later, the two settings of space bounded algorithms and of bounded-depth circuits remain at the forefront of research in unconditional derandomization. In this survey talk we review recent results and open questions, with an emphasis on the basic cases of width-3 branching programs and depth-2 circuits.
Bio of the Speaker
Luca Trevisan is a professor of electrical engineering and computer science at U.C. Berkeley and a professor of computer science at Stanford. Luca received his PhD in 1997 from the University of Rome La Sapienza. Before moving to California in 2000, Luca was a post-doc at MIT and at DIMACS, and an assistant professor at Columbia University.
Luca's research is in theoretical computer science, and most of his work has been in two areas: (i) the study of randomness and pseudorandomness in computation and in combinatorics; and (ii) the theory of probabilistically checkable proofs and its relation to the approximability of combinatorial optimization problems.
Luca received the STOC'97 Danny Lewin (best student paper) award, the 2000 Oberwolfach Prize, and the 2000 Sloan Fellowship. He was an invited speaker at the 2006 International Congress of Mathematicians in Madrid. |
