Wednesday, November 29, 2017

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.

Monday, November 27, 2017

Day 37

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

Monday, November 20, 2017

Day 36

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

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

Saturday, November 18, 2017

Day 35

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

Wednesday, November 15, 2017

Monday, November 13, 2017

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.

Friday, November 10, 2017

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


Wednesday, November 8, 2017

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.

Monday, November 6, 2017

Day 30

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

Friday, November 3, 2017

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.

Wednesday, November 1, 2017

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)