Lecture 43

Last lecture of the fall :(

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

Lecture 42

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

Lecture 41

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

One Complexity Theorist's View of Quantum Computing

Lectures 1 and 2 of John Watrous' lecture notes

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.

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.

Lecture 38

Conclude lecture series on PCP theorem with Proof of BLR test and PCP systems for quadratic-SAT.

Lecture 37

The Blum-Luby-Rubinfeld test and an introduction to Fourier analysis.

Lecture 36

The Long Code Test (Appendix B in Dinur)

Lecture 35

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

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).

Lecture 33

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

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).

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).

Lecture 30

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

Lecture 29

Arefin Huq on Natural Proofs

Lecture 28

Shen's Proof that IP = PSPACE

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.

Lecture 26

Finished Proof of Toda's Theorem and started on interactive proofs.

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

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.

Lecture 23

Proof that the Permanent is #P-complete (Valiant's Paper)

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.

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.

Lecture 20

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

Lecture 19

Lautemann's proof that BPP is in Σ^p₂∩Π^p₂.

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

Lecture 18

Arefin finished the switching lemma.

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

Lecture 16

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

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.

Lecture 14

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

Arefin will finish that proof on Wednesday.

Lecture 13

Razborov-Smolensky continued.

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

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 ACC⁰ 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 AC¹ which implies NL is in AC¹.

Lecture 10

Circuit Classes in increasing power
NCⁱ: Poly-size bounded-fan-in O(logⁱ n) depth
ACⁱ: Poly-size unbounded-fan-in O(logⁱ n) depth
ACCⁱ: ACⁱ with mod k gates for some k
TCⁱ: ACⁱ with majority gates
TCⁱ is contained in NCⁱ⁺¹

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

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. 

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

Lecture 7

The Polynomial-Time Hierarchy

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

Lecture 5

There exists oracle A and B such that P^A = NP^A and P^B ≠ NP^B

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

Homework 1 will be posted Friday

Lecture 4

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

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

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

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.

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}

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