Student Presentations

April 1: Abhishek Banerjee: A Pseudorandom Generator from any One-way Function by Johan Håstad, Russell Impagliazzo, Leonid A. Levin and Michael Luby

April 3: Peter Ralli: Possibilities and impossibilities in Kolmogorov complexity extraction by Marius Zimand

April 6: Dylan McKay: Poly-logarithmic independence fools AC0 circuits by Mark Braverman

April 8: Ben Cousins: Uniform Derandomization from Pathetic Lower Bounds by Eric Allender, Vikraman Arvind, Fengming Wang

April 10: Sadra Yazdanbod: Pseudo-random generators for all hardnesses by Chris Umans

April 13: John Stewart: Power from Random Strings by Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef Ronneburger

April 15: Emma Cohen: Kolmogorov's structure functions and model selection by Vereschagin and Vitanyi

April 17: No Class. Please attend Christos Papadimitriou's talk at the ARC 7 Seminar in MiRC 102

April 22: Ezgi Karabulut: Complexity and Mixed-Strategy Equilibria by Tai-Wei Hu

April 24: Abhishek Banerjee: Pseudorandom Generators for Polynomial Threshold Functions by Raghu Meka and David Zuckerman

April 27 (Klaus 3402): David Durfee: On the Complexity of Random Strings by Martin Kummer