Lecture 20

Nisan-Szegedy finish and connections to quantum

Lecture 19

On the degree of boolean functions as real polynomials by Noam Nisan and Mario Szegedy

Lecture 18

Quantum Teleportation

Lecture Notes by Greg Stoddard

Lecture 17

Shor's Algorithm continued

Lecture 16

Shor's Algorithm for factoring in quantum polynomial time

Lecture 15

Grover's Algorithm (search in N^1/2 queries)

Simon's Algorithm (finding s where f(x) = f(x⊕s))

Lecture Notes by George Askalidis

Lecture 14

Deutsch-Jousza algorithm

Lecture Notes by Aedan Maher

Lecture 13

Matrix Definitions of BPP and BQP

One complexity theorist's view of quantum computing

Scribe Notes by Prem Seetharaman

Lecture 12

Lecture by Madhav Suresh

Permanent is #P-Complete

Lecture 11

Matrix viewpoint for #P, Gap-P, #L and Gap-L

Lecture Notes by Darrell Hoy

Lecture 10

Toda's Theorem: PH in BPP^⊕P in P^Gap-P=P^PP

Lecture Notes by Darrell Hoy

Lecture 9

Toda-Ogihara: For every f in Gap^PH there is a g in Gap P s.t. f(x)=g(x,r) with high probability

Lecture Notes by Aedan Maher

Lecture 8

#P^NP in #coNP which randomly reduces to GapP.

Lecture 7

Mumuley-Vazirani-Vazirani Isolation Lemma
Valiant-Vazirani as a corollary

Lecture Notes: Madhav Suresh

Lecture 6

PP closed under union and intersection

Scribe Notes by Georgios Askalidis

Lecture 5

SPP is low for Gap-P and the other Gap Classes
Beginning of PP closed under union

Lecture Notes by Prem Seetharaman

PP is Closed under Intersection by Beigel, Reingold and Spielman
PP Is Closed under Truth-Table Reductions by Fortnow and Reingold

Lecture 4

#P and Gap Classes

Lecture Notes by Geoff Hill

Graph Automorphism in SPP (Kobler, Schoning, Turan)
Graph Isomorphism in SPP (Arvind-Kurer)

Lecture 3

Properties of GapP

Scribe Notes by Madhav Suresh

Lecture 2

Relationships between GapP and #P
Scribe Notes by Aedan Maher

Lecture 1

Definition and Properties of #P

Scribe Notes by George Askalidis

L. Fortnow. Counting complexity. In L. Hemaspaandra and A. Selman, editors, Complexity Theory Retrospective II, pages 81-107. Springer, 1997.

S. Fenner, L. Fortnow, and L. Li. Gap-definability as a closure property. Information and Computation, 130(1):1-17, 1996.

Course Information

Spring 2012

Lecturer: Lance Fortnow

Lectures: MWF 9:00-9:50 in Tech LG72

Description:

This course will cover a variety of topics in computational complexity including pseudorandomness, counting complexity, quantum computing and the structure of complete sets.

Prerequisite: EECS 335 or equivalent

There will be no textbook for the course. This blog will link to papers and scribe notes.

Grading will be based on scribe notes and a presentation of a recent paper in computational complexity.