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