# 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:

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