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

Lecture 32

Computational Depth

Lecture Notes by Emma Cohen

Computational depth: Concept and applications by Antunes, Fortnow, van Melkebeek and Vinodchandran

Low-Depth Witnesses are Easy to Find by Antunes, Fortnow, Pinto and Souto

Worst-Case Running Times for Average-Case Algorithms by Antunes and Fortnow

Lecture 31

Applications of Extractors

Lecture 30

Extractors

Lecture Notes by David Durfee

Relativizable pseudorandom generators and extractors by Peter Bro Miltersen

Extractors: optimal up to constant factors by Lu, Reingold, Vadhan and Wigderson

Lecture 29

Time-bounded sizes of sets using Kolmogorov complexity

Lecture Notes by John Stewart

Resource-bounded Kolmogorov complexity revisited by Buhrman, Fortnow and Laplante

Lecture 28

Introduction to resource-bounded complexity, C^t and CD^t

Lecture Notes by Ben Cousins

Lecture 27

Sophistication and data with no simple models

Lecture Notes by Abhishek Banerjee

Sophistication Revisited by Antunes and Fortnow