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.

Day 20

We introduced probabilistic Turing machines and talked about the classes BPP, RP and ZPP.

A language is in BPP if there is a probabilistic polynomial-time Turing machine such that for all x,

• If x is in L then the probability that M(x) accepts is at least 2/3.
• If x is not in L then the probability that M(x) accepts is at most 1/3.

A language is in RP if there is a probabilistic polynomial-time Turing machine such that for all x,

• If x is in L then the probability that M(x) accepts is at least 1/2.
• If x is not in L then the probability that M(x) accepts is 0.

A language is in ZPP if there is a probabilistic expected polynomial-time Turing machine such that for all x,

• If x is in L then the probability that M(x) accepts is 1.
• If x is not in L then the probability that M(x) accepts is 0.

We sketched why Composite testing is in RP and used Chernoff bounds to reduce the error in probabilistic algorithms to exponentially small. The exact statement of Chernoff bounds I gave in class was incorrect--we'll revisit on Friday.

Links:

• Computational Complexity of Probabilistic Turing Machines by John Gill. Defined the basic complexity classes. 
• Miller-Rabin primality test - An RP algorithm for composite testing works even when you have Carmichael numbers.
• Primes in P by Agrawal, Kayal and Saxena

Day 19

Finished proof of Razborov-Smolensky. Links in Day 18 post.

Kannan's non-constructive proof that Σ^p₂ does not have n^k-size circuit for any constant k.

Links:

• Circuit-size lower bounds and non-reducibility to sparse sets by Ravi Kannan
• Blog post on Kannan's result

Day 18

First half of Razborov-Smolensky proof that depth d circuits of Mod₃, AND, OR and NOT gates computing parity must have an exponential number of gates.

Links:

• We've been following the proof in Boppana-Sipser
• Algebraic methods in the theory of lower bounds for Boolean circuit complexity by Roman Smolensky
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition by Alexander Razborov

Day 17

P-complete sets including Monotone Circuit Value: Given a circuit of just AND/OR gates with variables set to the constants TRUE and FALSE, will the circuit evaluate to TRUE?

The major results in circuit complexity:

• Parity requires exponential-size circuits. 
• For distinct primes p and q, there is no polynomial-size constant-depth circuit with AND, OR, NOT and Mod_p gates that can compute the Mod_q function.
• Clique and Matching do not have polynomial-size monotone circuits even with arbitrary depth.
• *NEXP does not have constant-depth circuits with Mod_m gates for any fixed m, prime or composite. 

Links:

• The Complexity of Finite Functions by Ravi Boppana and Michael Sipser. A wonderful survey that covers definitions, results, proofs and references of the major circuit functions (except * which came after this survey).
• Nonuniform ACC Circuit Lower Bounds by Ryan Williams. This is the paper proving *.