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)