Day 27

We discussed closure properties of #P functions, some basic counting classes and the proof of Valiant Vazirani.

Let f(x,y) be a #P function and r(x) a polynomial-time computable function bounded by a polynomial in |x|.

• The sum of f(x,y) for all y with |y| = r(x) is in #P.
• The product of f(x,y) for all y with 1 ≤ y ≤ r(x) is in #P.
• (f(x,0) choose r(x)) is in #P.

L is in PP if there is a #P function f and a polynomial-time computable r such that

• x in L implies f(x) ≥ r(x)
• x not in L implies f(x) < r(x).

L is in ⊕P if there is a #P function f  such that

• x in L implies f(x) is odd
• x not in L implies f(x) is even

L is in UP if there is a #P function f  such that

• x in L implies f(x) = 1
• x not in L implies f(x) = 0

We also proved the Valiant-Vazirani theorem: There is a polynomial q and a probabilistic polynomial-time function f mapping CNF formulas to CNF formulas such that

• If φ is not satisfiable then f(φ) is never satisfiable.
• If φ is satisfiable then with probability at least 1/q(n), f(φ) has a unique satisfying assignment.

Link:

• NP is as easy as detecting unique solutions by Les Valiant and Vijay Vazirani. We gave Noam Ta-Shma's proof of Mulmuley-Vazirani-Vazirani isolation lemma. See also my blog post.

I also wanted to mention two upcoming talks by Joel Spencer, a great speaker and master of the probabilistic method. 

Day 26

Avi Wigderson, one of the giants of computational complexity, has released a PDF draft of his new book Mathematics and Computation. The book gives a philosophical and technical overview though a number of topics in computational complexity. Definitely worth downloading and reading if you are interested in the material in this course.

Today we proved Valiant's theorem that the permanent of a matrix is #P-complete.

•  The complexity of computing the permanent by Les Valiant
• #P-Completeness Via Many-One Reductions by Viktória Zankó. This paper gives a direct reduction from permanent with exponentially large weights to the permanent of a 0-1 matrix.

Day 25

Showed that AM in Π₂^P and MA in Σ₂^P∩Π₂^P and if AM is in co-NP then PH collapses to Σ₂^P.

This implies that if Graph Isomorphism is NP-complete then PH collapses to Σ₂^P.

Introduced counting complexity, #P and the Permanent.

A function f:{0,1}^*→ℕ is in #P if there is an NP machine M such that f(x) = the number of accepting paths of M(x).

The permanent of a matrix A is the sum over all permutations s of a_1s(1)...a_ns(n).

Day 24

Assignment 2 solutions have been posted on the T-Square resources page. A reminder that Assignment 3 is now available and is due November 1.

We gave the public-coin protocol for Graph Non-Isomorphism and showed that MA is contained in AM.

• Public-coin protocol write up by Jonathan Katz

Day 23

Assignment 3 has been posted on T-Square and due November 1. Assignment 2 grades have been released. Solutions to assignment 2 will be posted in the T-Square resources shortly.

Started our unit on Arthur-Merlin games.

Defined AM and gave the private-coin protocol for graph non-isomorphism and informally described the public coin protocol. We'll do a detailed public-coin protocol on Friday.

• Arthur-Merlin on Wikipedia
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes by László Babai and Shlomo Moran.
• Proofs that yield nothing but their validity and a methodology of cryptographic protocol design by Oded Goldreich, Silvio Micali and Avi Wigderson. Among other things this paper gives the first Arthur-Merlin protocol for graph isomorphism. 
• Private coins versus public coins in interactive proof systems by Shafi Goldwasser and Michael Sipser
• Graph Isomorphism in Quasipolynomial Time by László Babai

Day 22

Today we did the Schwartz-Zippel lemma and used it to give a co-RP algorithm for polynomial identity-testing.

We also showed that BPP is in P/poly and in Σ^P₂∪Π^P₂.

Links:

• Fast Probabilistic Algorithms for Verification of Polynomial Identities by Jack Schwartz
• Probabilistic algorithms for sparse polynomials by Richard Zippel
• Two theorems on random polynomial time by Len Adleman. Shows that BPP is in P/poly.
• A complexity theoretic approach to randomness by Michael Sipser and BPP and the polynomial hierarchy by Clemens Lautemann. Show BPP in  Σ^P₂∪Π^P₂
• Wikipedia articles (with good definitions and proofs) for BPP, Schwartz-Zippel, Polynomial Identity-Testing and BPP in  Σ^P₂∪Π^P₂.

Day 21

We did the proof of the Chernoff Bounds. Here is a detailed write-up.

We also discussed the polynomial identity testing question: Given a polynomial p(x1,...,xn) described by a circuit of product and sum gates, is that polynomial exactly zero?

To give a probabilistic algorithm for polynomial identity testing we looked at the Schwartz-Zippel lemma and gave part of the proof.