Date:  09:3010:10, Thursday, March 26, 2009 
Venue:  FIT Building 1315, Tsinghua University 
Title:  Derandomization of SpaceBounded Computational Classes

Speaker:  Elad Verbin 
Biography: 
Elad Verbin received his PhD in computer science in Tel Aviv University in Israel in 2007. He got Deutsch Award in 2006. He is interested in algorithms for combinatorial problems. His current interests are Compression, Sorting by Reversals and Transpositions, Colored Range Searching, and Matrix Multiplication. He is also interested in "strong techniques" used in computer science such as Samplingrelated approaches (specifically Markov Chain Monte Carlo), Methods based on Fourier Analysis, and Linear Programmingbased approaches.

Abstract: 
An outstanding question in computer science is the "L=RL?" question: whether any computation that uses logarithmic space and random bits, can be equivalently performed without any random bits, but still in logarithmic space. This question is one of the only questions in complexity theory that does not necessarily depend on getting an answer to the P vs. NP question.
In this talk, I will begin by discussing the two major approaches for proving L=RL. The first approach is to try to get a deterministic logspace algorithm for checking whether in an input directed wellmixing graph there is a path from vertex s to vertex t. This approach gained a big moral boost lately by Reingold's groundbraking algorithm for checking connectivity in undirected graphs, and by subsequent works.
The second approach is to try to build a pseudorandom generator for readonce polynomialwidth branching programs, using logarithmic seed. The best results in this approach are Nisan's generator on the one hand, and espilonbiased generators on the other hand. This approach seems to have been less successful so far, compared to the first approach.
In this talk I will (as much as time permits) outline both approaches, sketch what is known, and try to give an idea of the techniques involved. I will also try, if time permits, to briefly discuss some of the recent successes in the field.
