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