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

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

Lecture 22

Conclusion of Nisan-Wigderson including construction of designs.

Lecture Notes by Sadra Yazdanbod

Lecture 21

Overview of Nisan-Wigderson Construction
Guest Lecture by Arefin Huq

Hardness vs Randomness by Noam Nisan and Avi Wigderson

Lecture Notes by Sadra Yazdanbod

Lecture 20

Cryptographic versus Complexity pseudorandom generators

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

Pseudo-random generators for all hardnesses by Chris Umans

Lecture Notes by Peter Ralli

Lecture 19

BPP, Polynomial Identity Testing via Schwartz-Zippel, Intro to pseudorandom generators

Lecture Notes by David Durfee

Lecture 18

Kolmogorov v Entropy and Levin's Kt complexity and universal enumeration

Lecture Notes by Ben Cousins

Lecture 17

Linear relationships between K-complexity and Entropy

Inequalities for Shannon Entropy and Kolmogorov Complexity by Daniel Hammer, Andrei Romashchenko, Alexander Shen and Nikolai Vereshchagin

Lecture Notes by Ezgi Karabulut

Lecture 16

The close relationship between H(p) and E_p(K(x)).

THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
a classic 1970 paper by Zvonkin and Levin on Kolmogorov complexity. Proposition 5.1 gives the result that in the limit K(x1...xn)/n converges to H(p) where x's are drawn independently from p.

Lecture 15

Quick Primer on Entropy

Lecture Notes by Emma Cohen

Lecture 14

Hastad Switching Lemma (cont) and Circuit Lower Bounds
Lecturer: Arefin Huq

Lecture Notes by David Durfee

Lecture 13

Kolmogorov proof of Hastad switching lemma (Part 1)

Circuit Lower Bounds à la Kolmogorov by Fortnow and Laplante

Lecture Notes by John Stewart

Lecture 12

A Kolmogorov Complexity Proof of the Lovász Local Lemma

Lecture Notes by Abhishek Banerjee

Blog Post

Lecture 11

More on the universal distribution and intro on Lovasz Local Lemma.

Tardos-Moser paper A constructive proof of the general Lovász local lemma

Lecture notes by Peter Ralli

Lecture 10

Properties of the universal distribution

Lecture Notes by Emma Cohen

Lecture 9

m(x) = 2^-K(x) as a universal semi-computable semi-measure

Lecture Notes by Sadra Yazdanbod

Lecture 8

More Prefix-Complexity, Chaitin's Omega

Lecture Notes by David Durfee

Lecture 7

Properties of K-complexity

Lecture Notes by Nathan White

Lecture 6

K complexity - prefix-free (self-delimiting) complexity

Lecture Notes by John Stewart

Lecture 5

Symmetry of Information proof finished by Arefin
Runs of zeros in random strings
Lecture Notes by Ezgi Karabulut
The proof of symmetry of information is contained in the previous lecture notes.

Lecture 4

Symmetry of Information
Arefin Huq, Lecturer
Lecture Notes by Ezgi Karabulut

Lecture 3

Using Kolmogorov complexity to prove there are lots of primes and the power of random strings.

Lecture Notes by Peter Ralli

Lecture 2

Basic definitions and properties of Kolmogorov Complexity

Lecture 1

Introduction to Randomness and Kolmogorov Complexity

Slides

Lecture notes by Ben Cousins