Friday, December 4, 2015

Lecture 43

Last lecture of the fall :(

We covered Shor's algorithm for factoring numbers in quantum polynomial time, best explained in his paper.

Wednesday, December 2, 2015

Lecture 42

Quantum Algorithms: Deutsch-Jozsa, Simon, Grover
John Watrous lecture notes, Lecture 5, 6, 12 and 13.

Monday, November 30, 2015

Lecture 41

Introduction to Quantum Computing: Basic quantum transformations and definition of BQP.

Lectures 1 and 2 of John Watrous' lecture notes

Monday, November 23, 2015

Lecture 40

Remember to enter your CIOS comments for this course and all your courses.

Laszlo Babai's first talk on his new graph isomorphism algorithm is now on video. Babai is an excellent lecturer and I highly recommend finding 100 minutes to watch the talk.

Today we covered time-space tradeoffs for SAT from the papers:
Time-space tradeoffs for satisfiability by L. Fortnow. .
Time-space lower bounds for satisfiability by L. Fortnow, R. Lipton, D. van Melkebeek, and A. Viglas.

Friday, November 20, 2015

Lecture 39

Assignment 4, our last assignment, has been posted to T-Square and is due on Wednesday, December 2 at 8 PM. There will be no final exam.

Arefin Huq covered zero-knowledge for Sudoku from the paper Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles by Ronen Gradwohl, Moni Naor, Benny Pinkas and Guy N. Rothblum.

He also discussed bit commitment and presented the zero-knowledge proof for graph isomorphism, comparing and contrasting with the Arthur-Merlin protocol for graph non-isomorphism.

Friday, November 13, 2015

Wednesday, November 11, 2015

Lecture 35

A sketch of the proof of the amplification lemma (Lemma 6.1 in Dinur). Introduction to the assignment tester.

Monday, November 9, 2015

Lecture 34

Second part of prep that converts bounded degree regular graph to an expander with self-loops (Definition 4.3 and Lemma 4.4 of Dinur).

Construction of Graph Powering for Amplification step (follows after Theorem 1.7 in Dinur).

Friday, November 6, 2015

Lecture 33

Proof of the first step of the preprocessing lemma (Lemma 4.2 in Dinur).

Wednesday, November 4, 2015

Lecture 32

Continuation of PCP proof. Laid out the three lemmas: Preprocessing (Lemma 1.9 in Dinur's paper), Amplification and Composition. Gave construction of the first phase of the preprocessing lemma (Def 4.1).

Monday, November 2, 2015

Lecture 31

We have begun working through Irit Dinur's proof of the PCP theorem by gap amplification. Today we defined constraint graphs, stated the main theorem (Theorem 1.7) and defined expander graphs (Section 2.1).

Friday, October 30, 2015

Lecture 30

Introduced the PCP Theorem (Arora-Lund-Motwani-Sudan-Szegedy). Next week we will start the proof due to Irit Dinur.

Wednesday, October 21, 2015

Lecture 27

In lieu of a lecture on Friday, please attend the Sunbird panel in the Klaus Atrium. The instructor will hold office hours from 4-5 PM for those who have questions about Assignment 3 due Monday.

In class we discussed the proof that there exist interactive proofs for co-NP, P#P and thus every language in the polynomial-time hierarchy. On Monday we'll show how to extend to IP = PSPACE.

Monday, October 19, 2015

Friday, October 16, 2015

Lecture 25

Assignment 3 has been posted on T-Square. Due on Monday, October 26 at 5 PM.

Valiant-Vazirani to show NP in BPP⊕P

⊕P = ⊕P⊕P (Papadimitriou-Zachos)

The first part of Toda's theorem that the polynomial-time hierarchy is in BPP⊕P

Wednesday, October 14, 2015

Lecture 24

Proof of the Isolation Lemma and its application to show that solving satisfiability on formulas with at most one satisfying assignment implies NP = RP. Details and links in my blog post.

Friday, October 9, 2015

Wednesday, October 7, 2015

Lecture 22

Assignment 2 has been graded. Feedback available on T-Square.

Went over the solution to the third problem: NP in co-NP/poly collapses the polynomial-time hierarchy to the third level. Full proof (and more) in Some consequences of non-uniform conditions on uniform classes by Chee Yap.

Also finished off proof that graph non-isomorphism is in AM.

Started counting complexity. Introduced #P and the permanent function.

Monday, October 5, 2015

Lecture 21

Graph Non-Isomorphism is in AM
Proof in Section 3 of this paper.

We also showed that if co-NP is contained in AM then the polynomial-time hierarchy collapses to the second level. Combined these results show that if Graph Isomorphism is NP-complete then the polynomial-time hierarchy collapses. This is the best evidence we have that GI is not NP-complete.

Friday, October 2, 2015

Lecture 20

Definitions of MA and AM
NPBPP in MA in AM in NPBPP
NP in BPP implies PH in BPP
MA in ΠP2
AM in ΣP2
AM and MA with perfect completeness (no error if x in L)
Some details in Section 2 of Katz Notes

Wednesday, September 30, 2015

Lecture 19

Lautemann's proof that BPP is in Σp2∩Πp2.

Informal notion of Merlin-Arthur games and example of proof of graph non-isomorphism.

Monday, September 28, 2015

Friday, September 25, 2015

Lecture 17

Assignment 2 posted on T-Square due October 5 at 5 PM

Probabilistic Complexity Classes: PP, BPP, RP and ZPP.
Can assume error is 1-2^{q(n)} for any polynomial q
Showed NP in PP, RP in BPP in P/poly
HW to show ZPP = RP ∩ co-RP


Wednesday, September 23, 2015

Lecture 16

Arefin finished Barrington's Theorem and started Håstad switching lemma.

Monday, September 21, 2015

Lecture 15

Randomized Algorithms introduced with primality testing based on Fermat's Little Theorem. Fails to work on Carmichael Numbers so need a different test: Miller-Rabin. Primality was shown to have a deterministic polynomial-time solution  in Agrawal-Kayal-Saxena.

Homework assignment two will be distributed on Friday.

Friday, September 18, 2015

Lecture 14

Conclusion of Razborov-Smolenksy and start of Barrington's Theorem that NC1 has poly-size bounded-width branching programs. Proofs in Boppana-Sipser.

Arefin will finish that proof on Wednesday.

Wednesday, September 16, 2015

Monday, September 14, 2015

Lecture 12

Razborov-Smolensky proof that Parity cannot be computed by poly-size constant depth circuits with Mod-3 gates.

Section 3.8 of Boppana-Sipser

Friday, September 11, 2015

Lecture 11

Assignment 1 is returned via T-Square. Above a 50 is a reasonable grade. We discussed the solution to showing that 3:a->b which you can find as Theorem 2 here.

We discussed many circuit results, the ones before 1989 with proofs are summarized nicely in
The Complexity of Finite Functions by Boppana and Sipser

Two more recent results:
NEXP not in ACC0 by Ryan Williams
PH infinite relative to a random oracle  by Benjamin Rossman, Rocco Servedio and Li-Yang Tan

We also showed matrix multiplication is in AC1 which implies NL is in AC1.




Wednesday, September 9, 2015

Lecture 10

Circuit Classes in increasing power
NCi: Poly-size bounded-fan-in O(logi n) depth
ACi: Poly-size unbounded-fan-in O(logi n) depth
ACCi: ACi with mod k gates for some k
TCi: ACi with majority gates
TCi is contained in NCi+1

For more about these or any classes, see the Complexity Zoo.

Friday, September 4, 2015

Lecture 9

By popular demand, Assignment 1 deadline has been extended to Tuesday 9 AM. Extra credit to those who turn it in by the original deadline of 5 PM today.

Defined P/poly and showed the equivalence to languages accepted by poly-size circuits. Karp-Lipton Theorem showing that if NP is in P/poly then the polynomial time hierarchy collapses to the second level. 

Wednesday, September 2, 2015

Lecture 8

Circuit Complexity - P-completeness of circuit value. Polynomial-size circuit families

Completeness in the Polynomial-Time Hierarchy: A Compendium by Marcus Schaefer and Chris Umans

Friday, August 28, 2015

Lecture 6

Alternation

True Quantified Boolean Formulas (TQBF sometimes written QBF) is PSPACE-Complete (Proof)
Similar to the proof of Savitch's Theorem

Introduced Alternating Turing Machines
All based on paper Alternation by Chandra, Kozen and Stockmeyer

HW1 is now posted, due Friday September 4 at 5 PM on T-Square

Ground Rules for assignments
You can work together but should write up solutions in your own words
Best to solve the problems without outside help but if you do look up the solution please cite the source and write up the solution in your own words



Wednesday, August 26, 2015

Lecture 5

There exists oracle A and B such that PA = NPA and PB ≠ NPB

Relativizations of the P =? NP Question by Baker, Gill and Solovay

Homework 1 will be posted Friday



Monday, August 24, 2015

Lecture 4

Mahaney's Theorem: There are no sparse NP-complete sets unless P = NP

Introduced oracle Turing machines. Next class: Baker-Gill-Solovay

Friday, August 21, 2015

Lecture 3

Ladner's Theorem that, assuming P is different than NP, there is a language L in NP, L not in P and L not NP-complete.

Two Proofs of Ladner's Theorem by Lance Fortnow

Wednesday, August 19, 2015

Lecture 2

Assignment 0 is posted and should be submitted via T-Square. Due by August 20 at 5 PM. If you are not registered and want access to the T-Square site please contact the instructor.

NP-completeness and Cook's Theorem.

A is reducible to B if there is a polynomial-time function f such that

  • x in A implies f(x) in B
  • x not in A implies f(x) not in B


L is NP-complete if

  1. L is in NP, and
  2. For all A in NP, A is reducible to L


We will show that CNF-SAT is NP-complete. Let A be a language in NP accepted by a nondeterministic Turing machine M. Fix an input x. We will create a 3CNF formula φ that will be satisfiable if and only if there is a proper tableau for M and x.
Let m be the running time of M on x. m is bounded by a polynomial in |x| since A is in NP. m is also a bound on the size of the configurations of M(x).
We will create a set of Boolean variables to describe a tableau and a set of clauses that will all be true if and only if the tableau is proper. The variables are as follows.
  • qij: true if confi is in state j.
  • hik: true if the head in confi is at location k.
  • tikr: true if the tape cell in location k of confi has element r.
We create four clause groups to check that the tableau is proper.
  1. Every configuration has exactly one state, head location and each tape cell has one element.
  2. conf0 is the initial configuration.
  3. confm is accepting.
  4. For each i≤m, confi+1 follows from confi in one step.
1. We will just do this for states. The others are similar. Suppose we have u possible states. 
Each configuration in at least one state. For each i we have
qi0 OR qi1 OR ... OR qiu
Each configuration in at most one state. For each i and possible states v and w, v≠w
(NOT qiv) OR (NOT qiw)
2. Let x=x1...xn, b the blank character and state 0 the initial state. We have the following single variable clauses,
q00
h01
t0ixi for i≤n
t0ib for i>n
3. Let a be the accept state. We need only one single variable clause.
qma
4. We need two parts. First if the head is not over a tape location then it should not change.
((NOT hik) AND tikr)→ ti(k+1)r
Now this doesn't look like an OR of literals. We now apply the facts that P→Q is the same as (NOT P) OR Q and NOT(R AND S) is equivalent to (NOT R) OR (NOT S) to get
hik OR (NOT tikr) OR t(i+1)kr
At this point none of the formula has been dependent on the machine M. Our last set of clauses will take care of this. Recall the program of a Turing machine is a mapping from current state and tape character under the head to a new state, a possibly new character under the head and a movement of the tape head one space right or left. A nondeterministic machine may allow for several of these possibilities. We add clauses to prevent the wrong operations.
Suppose that the following is NOT a legitimate transition of M: In state j and tape symbol r, will write s, move left and go to state v. We prevent this possibility with the following set of clauses (for all appropriate i and k).
(qij AND hik AND tikr)→ NOT(t(i+1)ks AND hi(k-1) AND q(i+1)v)
which is equivalent to
(NOT qij) OR (NOT hik) OR (NOT tikr) OR (NOT t(i+1)ks) OR (NOT hi(k-1)) OR (NOT q(i+1)v)
We do this for every possible illegitimate transition. Finally we just need to make sure the head must go one square right or left in each turn.
(NOT hik) OR h(i+1)(k-1) OR h(i+1)(k+1)
Just to note in the above formula we need special care to handle the boundary conditions (where k is 1 or m) but this is straightforward.

Monday, August 17, 2015

Lecture 1

Overview of the course. Definitions of Turing machine, deterministic and nondeterministic time and space complexity.

Turing Machine
Finite control: set of states
Move: scan symbol, write symbol, move left or right, change state
M = (Q,Σ,Γ,δ,q0,B,qacc,qrej)
Q finite set of states
Σ finite alphabet B is not in Σ
Γ finite tape alphabet: Σ is a strict subset of Γ (no B)
q0 - initial state
qacc,qrej halting states: accept and reject

δ maps Q×Γ→Q×Γ×{L,R}


Tuesday, March 31, 2015

Course Overview

CS 6520 Computational Complexity
Fall 2015


Instructor: Lance Fortnow

Time: MWF 9:05-9:55
Room: Klaus 1456

Description: This course will give an overview of advanced topics in computational complexity including the P versus NP problem, the structure of NP, the polynomial-time hierarchy, circuit complexity, randomness, counting, interactive and probabilistically checkable proofs.

Detailed list of topics

Prerequisites: A basic knowledge of Turing machines and the P v NP problem at the level of CS 4510.

Textbook: None. Computational Complexity by Arora and Barak cover much of the material from the course but we won't be following them.

Coursework: Assignments roughly every other week. This is a theoretical course and assignments will be problem solving and will not involve any programming.

Course Website: gtccf15.blogspot.com