Computational Complexity (Spring 2007)

This course describes attempts to answer a fundamental question of CS namely: What can computers solve efficiently?

Some Bibliography:

This course does not have a textbook. However, every week following the lectures I will post link(s) to relevant material that is available online. Most of this material is going to be from two books that are currently being written:

• Draft of book by Oded Goldreich.
• Draft of book by Sanjeev Arora and Boaz Barak.

Some of the topics (at least in the beginning of the course) are also covered in the following books.

• Computational Complexity by Christos Papadimitriou.
• Introduction to the theory of computation by Michael Sipser.

Exercises:

• Exercise 1 : Submission date 22/3/2007.
• Exercise 2 : Submission date 15/4/2007.
• Exercise 3 : Submission date  3/6/2007.
• Exercise 4 : (Final exercise) submission date 12/7/2007.

Lectures:

• Lecture 1:

   High level overview of goals and achievements of complexity theory.

   A quick reminder of P and NP. (See for example Sipser's book or the relevant chapters in the drafts).

   Space complexity (Part I chapter 4 in Arora-Barak, or Chapter 5 in Goldreich. Most of this material is also available in Sipser's and Papadimitriou's books).

  • 3-SAT in linear space.
  • Definition of TMs that run in space << n.
  • Examples: Addition in space O(log n).
  • Definition of nondeterministic machines with space << n. (The certificate is given on a read-only one-way access tape that does not count as memory).
  • directed and undirected connectivity in nondeterministic space O(log n).
  • A randomized algorithm for undirected connectivity (no proof yet).

   

• Lecture 2: Space complexity (Part I chapter 4 in Arora-Barak, or Chapter 5 in Goldreich. Most of this material is also available in Sipser's and Papadimitriou's books).

  • Definition of L,NL,PSPACE,NPSPACE.

  • NSPACE(s(n)) in TIME(2^{O(s(n))}) (configuration graphs). (corollary: NL in P).

  • Reminder: reductions and completeness.

  • Subtle point: A logspace reduction cannot store its output.

  • dPATH is complete for NL.

  • Savich's theroem: NSPACE(s(n)) in SPACE(s(n)^2). (corollary NPSPACE=PSPACE).

  • Quantified boolean formulae and the language TQBF.

  • TQBF is PSPACE complete.

  • NL=coNL (proof next week).

   

• Lecture 3:
  • Space complexity continued: Proof that NL=coNL.
  • Diagonalization: (Part I chapter 3 in Arora-Barak, or Chapet 4 in Goldreich).
  • Reminder of the idea of diagonalization.
  • The deterministic time hierarchy theorem. (Corollary P <> EXP).
  • The space time hierarchy theorem. (Corollary L<>PSPACE).
  • The nondeterministic time hierarchy theorem. (Delayed Diagonaliztion).

   

• Lecture 4:
  • Oracles and relativization. (Definitions and examples).
  •  The statement P=NP does not relativize. (Part I chapter 3 in Arora-Barak).
  • Philosophical discussion of the meaning of relativization.
  • Definition of the polynomial time hierarchy. (In several equivalent definitions). (Part I chapter 4 in Arora-Barak or 3.2 in Goldreich).
  • The hierarchy collapse if Pi_i=Sigma_i or if PH has a complete problem.
  • SAT not in TISP(n^{1.2},n^{0.2}) (statement only, proof next week).

   

• Lecture 5:
  • SAT not in TISP(n^{1.2},n^{0.2}). (We've done the proof and explained the overall approach of indirect diagonalization).
  • Definition of Boolean circuits and families of Boolean circuits. The class PSIZE.
  • Thm: For every TM M that runs in time t(n) and input length n there is a circuit C of size ct(n)^2 that is equivalent to M on inputs of length n.
  • Discussion on nonuniform computation. Circuits can compute undecidable languages.
  • Uniform circuits and the equivalence of L-uniform polynomial size circuits to P.
  • Nonuniform Turing machines, the class P/poly and PSIZE=P/poly.
  • Approach: Showing that NP<>P by showing that NP isn't in P/poly.
  • Karp-Lipton theorem: NP in P/poly implies PH=\Sigma_2.
  • Reminder: decision versus serach versions for problems in NP.
  • If NP in P/poly then NP search problems can be solved by poly-size circuits.

• Lecture 6: (Boolean Circuits continued, the material can be found in Arora-Barak Part I, chapter 6).
  • Proof of the Karp-Lipton Theorem.
  • The class NC and its relation to distributed computing.
  • Parity is not in AC0. (We saw the proof by Razborov-Smolensky, see for example Arora-Barak Part II chapter 13, section 13.2).
  • Natural properties and the Razborov-Rudich negative result (statement only).

• Lecture 7: Randomized Algorithms (Examples).
  • Reminder of probability theory (probability space, random variables expectation).
  • Random sampling and the Chernoff inequality.
  • Example: file comparison using low comnication.
  • Example: Polynomial identitiy testing.
  • Example: Primality testing (outline only).
  • Example: A randomized logspace algorithm for uPATH.

• Lecture 8: Randomized algorithms (continued). (The materilal can be found in Arora-Barak, part I chapter 7).
  • Definition of probabilistic algorithms and complexity classes: BPP, RP, ZPP and relationships between them.
  • Discussion: The power of probabilistic algorithms. We think that BPP=P but do not know to show that BPP<>NEXP.
  • BPP in P/poly
  • BPP in Sigma_2. Corollary if NP=P then BPP=P.
  • Introduction to probabilistic proof systems.

• Lecture 9: Interactive proofs.
  • Definition of interactive proofs and the class IP.
  • Observations regading IP:
    • NP in IP in PSPACE.
    • IP = NP when verifier is deterministic.
    • Prover's optimal strategy can be found in PSPACE.
    • Amplification of success probability (both in parallel and sequentially).
  • Graph non isomorphism in IP.
  • coNP in IP:
    • Arithmetization.
    • The sumcheck protocol.
    • What is nonrelativizing here?
  • IP=PSPACE. Modifications required to the sumcheck protocol.
  • Discussion: public coins and private coins.
  • Theorem: Any private coin proof can be simulated by a public coin proof with O(1) additional rounds. (We only saw a sketch for GNI).
  • The class AM=IP[O(1) rounds and public coins].

   

• Lecture 10: Interactive proofs continued.
  • MA in AM and AM[k]=AM[1].
  • AM can w.l.o.g. have perfect completeness.
  • Corollary AM in Pi_2.
  • Corollary: If Graph isomorphism is NP complete then PH collapses.
  • PCP(r(n),q(n)).
  • The PCP theorem: NP=PCP(O(log n),O(1)).
  • Approximation algorithms. (Example MAX-3-SAT has a a 7/8 approximation algorithm when all 3 literals are different).
  • The problem max-q-CSP.
  • Relationship between PCP and hardness of approximation: Max-q-CSP cannot be approximated within a constant factor if NP<>P.
  • The PCP theorem as a gap amplifying reduction.
  • Discussion: PCP as a robust version of the Cook-Levin theorem and intuitive connection to error-correcting codes.