Raghu Meka: Pseudorandomness- old problems, new methods, and current challanges
Thursday, March 3, 2016 - 2:45pm to 3:45pm
Refreshments:
Light Refreshments at 3:50pm, D-463 (Star)
Location:
D-463 Star
Speaker:
Raghu Meka, UCLA
Seminar group:
Abstract: In this talk I will survey recent results on two classical questions in complexity theory: derandomizing small-space algorithms and lower bounds for constant-depth circuits. I will highlight a new technique---"iterative simplification"---for building pseudorandom generators (PRGs) leading up to nearly-optimal PRGs for several well-studied test functions including halfspaces and read-once CNFs.
I will also emphasize a few open problems and challenges (among many) that seem to test the limits of our knowledge and tools in derandomization.