Lecture 17

Valiant-Vazirani

Scribe Notes by Greg Stoddard

Lecture 16

Counting Complexity

Scribe Notes by Adam Kalinich

Lecture 15

Barrington's Theorem

Lecture and Scribe Notes by Arefin Huq

Lecture 14

Assignment 3 due Wednesday, November 3.

Topic: Arthur-Merlin Games.

Scribe Notes by David Barbella

Lecture 13

The Complexity of BPP

Scribe Notes by Michele Budinich

Lecture 12

Natural Proofs, BPP in P/poly

Scribe Notes by  Manolis Pountourakis

• Natural Proofs. Original paper by Razborov and Rudich
• Lance's Natural Proofs Blog Post

Lecture 11

Razborov-Smolensky Part 2

Lecture by Arefin Huq

See notes from Lecture 10.

Lecture 10

Razborov-Smolensky Part I

Lecture and Scribe Notes by Arefin Huq

Lecture 9

Assignment 2 Posted and due Wednesday, October 20.

Topics: Time-space tradeoffs, introduction to probabilistic classes.

Scribe Notes by Darrell Hoy

Two proofs of Schwartz-Zippel

• Wikipedia proof
• Moshkovitz proof

Lecture 8

Topics: Circuits between AC⁰ and NC¹, lower bound theorems.
Scribe notes by Tom Hayden

Lecture 7

Topics: The world between NC¹ and AC¹, PRAMs

Scribe Notes by Adam Kalinich

Lecture 6

Topic: Circuit Complexity

Scribe Notes by Nima Haghpanah

Papers:

• Furst-Saxe-Sipser, Ajtai: Parity not in AC⁰
• Yao: Exponential lower bounds for Parity
• Hastad: Tight bounds for Parity
• Razborov-Smolensky: Lower bounds for Mod_p with Mod_q circuits
• Razborov: Monotone Lower Bounds for Clique
• Fortnow-Laplante: Razborov's proof of Hastad's result via Kolmogorov complexity

Lecture 5

Scribe Notes by David Barbella

Topics: Polynomial-Time Hierarchy, P/poly

Papers Mentioned:

• Karp-Lipton: PH collapses to second level if NP in P/poly
• Buhrman-Hitchcock: PH collapses to third level if there are subexponential-sized NP-complete sets