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

Lecture 26

Model Selection via Kolmogorov Complexity

Lecture Notes by Abhishek Banerjee

Kolmogorov's structure functions and model selection by Vereschagin and Vitanyi

Lecture 25

NEXP in P/poly iff NEXP = EXP = MA

In search of an easy witness: exponential time vs. probabilistic polynomial time by Impagliazzo, Kabanets and Wigderson

Lecture 24

Sign Up for Student Presentations

Implications of full derandomization including Graph Iso in NP ∩ co-NP under reasonable assumptions

Lecture Notes by Peter Ralli

Private coins versus public coins in interactive proof systems by Goldwasser and Sipser

Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses by Klivans and van Melkebeek

Lecture 23

Removing the approximation assumption for derandomization.

Lecture Notes by Emma Cohen

Yao XOR Lemma course notes from Ronitt Rubinfeld

BPP has subexponential time simulations unless EXPTIME has publishable proofs by Babai, Fortnow, Nisan and Wigderson

P = BPP if E requires exponential circuits: derandomizing the XOR lemma by Impagliazzo and Wigderson