Date: 09:30-10:10, Thursday, March 26, 2009
   
Venue: FIT Building 1-315, Tsinghua University
   
Title: Derandomization of Space-Bounded 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 Sampling-related approaches (specifically Markov Chain Monte Carlo), Methods based on Fourier Analysis, and Linear Programming-based 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 well-mixing 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 read-once polynomial-width branching programs, using logarithmic seed. The best results in this approach are Nisan's generator on the one hand, and espilon-biased 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.

 

 


[Close]