Day 40

Final Day of Class. It's been a good ride.

Assignment 4 has been graded and solutions on the resource page. Assignment 5 is due December 13. Because of the limited time for grading there will be no extensions and a 1 point/hour late penalty. If you have any other uncompleted assignments they will also be due December 13 for partial credit.

We covered a Kolmogorov complexity version of Robin Moser's proof of the Lovász local lemma.

• A constructive proof of the Lovász local lemma by Robin Moser
• A Kolmogorov Complexity Proof of the Lovász Local Lemma (My blog post)

Hope you enjoyed the class and may all your lives be complete!

Day 39

Prefix-free complexity and the universal measure

• Sections 5 and 6 from my Kolmogorov Complexity survey
• Lecture notes with more details.

Day 38

Assignment 5 has been posted and due December 13.

Assignment 4 is still being graded but solutions have been posted on the T-Square resources page.

Introduction to Kolmogorov complexity with basic results, applications to primes and mathematical logic.

• Kolmogorov Complexity by Lance Fortnow

Day 37

Guest lecture by DeVon Ingram on the Sensitivity Conjecture and GKS games.

• A New Approach to the Sensitivity Conjecture by Justin Gilmer, Michal Koucký and Michael Saks

Day 36

The following are polynomial related for any function f:{0,1}ⁿ→{0,1}.

• Decision Tree Complexity (deterministic query complexity)
• Certificate Complexity
• Block Sensitivity
• Degree of approximate polynomial
• Degree of exact polynomial
• Quantum query complexity

Links:

• Quantum lower bounds by polynomials by Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca and Ronald de Wolf
• On the degree of boolean functions as real polynomials by Noam Nisan and Mario Szegedy

Day 35

Shor's Algorithm - polynomial-time quantum algorithm for factoring

• Algorithms for quantum computation: discrete logarithms and factoring by Peter Shor

Day 34

More quantum: Deutsch-Jozsa, Grover and Simon

• Rapid solution of problems by quantum computation by David Deutsch and Richard Jozsa
• A fast quantum mechanical algorithm for database search by Lov Grover
• On the Power of Quantum Computation by Dan Simon

Day 33

Introduction to Quantum Computing. Gave the matrix definition of quantum machines (see my paper below) and described the Hadamard matrix and its properties.

• One complexity theorist's view of quantum computing by Lance Fortnow

Day 32

In this class we showed how MIP = NEXP implies lower bounds on approximating the clique problem and how this led to the PCP theorem. The PCP theorem states that every language in NP has  probabilistically checkable proof where the verifier uses O(log n) random bits and makes only a constant number of queries to a proof that just returns bit. Here is a strong version.

For any constant α > 7/8, there is a polynomial-time computable function f mapping 3-CNFs to 3-CNFs such that for all formula φ,

• If φ is satisfiable then f(φ) is satisfiable.
• If φ is not satisfiable then every assignment to f(φ) satisfies at most an α-fraction of the clauses.

The proof is an assignment, O(log n) random coins are used to pick a clause and only the 3-queries to the variables of that clause are needed.

We also talked about the Unique Games conjecture. 

Links:

• Interactive proofs and the hardness of approximating cliques by Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra and Mario Szegedy
• Proof verification and the hardness of approximation problems by Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan and Mario Szegedy. First proof of the PCP theorem.
• The PCP theorem by gap amplification by Irit Dinur. A simpler more combinatorial proof of the PCP theorem.
• Some optimal inapproximability results by Johan Håstad. Gets the tight result for 3-SAT above.
• On the power of unique 2-prover 1-round games by Subhash Khot. This paper introduces unique games.
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs? by Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell
• Compendium of NP Optimization Problems. Good list of problems and their best known approximations and limitations.

Day 31

Assignment 3 has been graded and solutions posted on the T-Square resource page. Assignment 4 has been posted and is due November 20.

We showed that MIP (in PCP form) was equal to NEXP.

• Non-deterministic exponential time has two-prover interactive protocols by László Babai, Lance Fortnow and Carsten Lund
• Robust Characterizations of Polynomials with Applications to Program Testing by Ronitt Rubinfeld and Madhu Sudan. This is a more direct and robust low-degree test.

Day 30

We showed that IP = PSPACE via the Shen proof and introduced the MIP model.

• IP = PSPACE by Adi Shamir
• IP =PSPACE: Simplified proof by Alexander Shen
• On the power of multi-prover interactive protocols by Lance Fortnow, John Rompel and Michael Sipser

Day 29

We gave the proof that co-NP and P^#P have interactive protocols (Arthur-Merlin games with unbounded rounds). We will generalize to PSPACE on Monday.

• Algebraic methods for interactive proof systems by Carsten Lund, Lance Fortnow, Howard Karloff and Noam Nisan

Day 28

We proved Toda's theorem that PH is in P^#P.
Along the way we needed:

• NP in BPP^⊕P (follows from Valiant-Vazirani discussed last class)
• ⊕P^⊕P = ⊕P (Papadimitrious Zachos)
• NP in BPP implies PH in BPP (Assignment 3)

Links

• PP is as Hard as the Polynomial-Time Hierarchy by Seinsuke Toda
• A Simple Proof of Toda's Theorem by Lance Fortnow
• Two remarks on the power of counting by Christos Papadimitriou and Stathis Zachos

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.