Lecture 30

Introduced the PCP Theorem (Arora-Lund-Motwani-Sudan-Szegedy). Next week we will start the proof due to Irit Dinur.

Lecture 29

Arefin Huq on Natural Proofs

Lecture 28

Shen's Proof that IP = PSPACE

Lecture 27

In lieu of a lecture on Friday, please attend the Sunbird panel in the Klaus Atrium. The instructor will hold office hours from 4-5 PM for those who have questions about Assignment 3 due Monday.

In class we discussed the proof that there exist interactive proofs for co-NP, P^#P and thus every language in the polynomial-time hierarchy. On Monday we'll show how to extend to IP = PSPACE.

Lecture 26

Finished Proof of Toda's Theorem and started on interactive proofs.

Lecture 25

Assignment 3 has been posted on T-Square. Due on Monday, October 26 at 5 PM.

Valiant-Vazirani to show NP in BPP^⊕P

⊕P = ⊕P^⊕P (Papadimitriou-Zachos)

The first part of Toda's theorem that the polynomial-time hierarchy is in BPP^⊕P

Lecture 24

Proof of the Isolation Lemma and its application to show that solving satisfiability on formulas with at most one satisfying assignment implies NP = RP. Details and links in my blog post.

Lecture 23

Proof that the Permanent is #P-complete (Valiant's Paper)

Lecture 22

Assignment 2 has been graded. Feedback available on T-Square.

Went over the solution to the third problem: NP in co-NP/poly collapses the polynomial-time hierarchy to the third level. Full proof (and more) in Some consequences of non-uniform conditions on uniform classes by Chee Yap.

Also finished off proof that graph non-isomorphism is in AM.

Started counting complexity. Introduced #P and the permanent function.

Lecture 21

Graph Non-Isomorphism is in AM
Proof in Section 3 of this paper.

We also showed that if co-NP is contained in AM then the polynomial-time hierarchy collapses to the second level. Combined these results show that if Graph Isomorphism is NP-complete then the polynomial-time hierarchy collapses. This is the best evidence we have that GI is not NP-complete.

Lecture 20

Definitions of MA and AM
NP^BPP in MA in AM in NP^BPP
NP in BPP implies PH in BPP
MA in Π^P₂
AM in Σ^P₂
AM and MA with perfect completeness (no error if x in L)
Some details in Section 2 of Katz Notes