Friday, October 30, 2015

Lecture 30

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

Wednesday, October 21, 2015

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.

Monday, October 19, 2015

Friday, October 16, 2015

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

Wednesday, October 14, 2015

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.

Friday, October 9, 2015

Wednesday, October 7, 2015

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.

Monday, October 5, 2015

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.

Friday, October 2, 2015

Lecture 20

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