Pseudorandomness via iterative simplification

The use of randomness is fundamental in algorithms and complexity theory. However, in spite of the prevalence of randomized algorithms, it is still unknown if randomness is essential for the design of efficient algorithms. This is one of the foremost open problems in computer science.

In this talk, I will address two important facets of this question: derandomizing small-space algorithms and constant-depth circuits. I will highlight a new technique---"iterative simplification"---for building more powerful pseudorandom generators (PRGs) from simpler ones leading up to nearly-optimal PRGs that overcome several longstanding bottlenecks within the above classes. 

Raghu Meka received his PhD at UT Austin under the guidance of David Zuckerman. After that, he spent two years in Princeton as a postdoctoral fellow at the Institute for Advanced Study with Avi Wigderson and at DIMACS, Rutgers. Following that, he spent a year as a researcher at Microsoft Research, Silicon Valley Lab. He is currently an Assistant Professor in the Computer Science Department at UCLA. He is broadly interested in complexity theory, learning, and probability theory.