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 AroraBarak,
or Chapter 5 in Goldreich. Most of this material is also available in
Sipser's and Papadimitriou's books).
 3SAT 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 readonly oneway 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
AroraBarak, 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 AroraBarak, 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 AroraBarak).
 Philosophical discussion of the meaning of relativization.
 Definition of the polynomial time hierarchy. (In several
equivalent definitions). (Part I chapter 4 in AroraBarak 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 Luniform
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.
 KarpLipton 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
polysize circuits.
 Lecture 6: (Boolean Circuits continued, the material can
be found in AroraBarak Part I, chapter 6).
 Proof of the KarpLipton Theorem.
 The class NC and its relation to distributed computing.
 Parity is not in AC0. (We saw the proof by
RazborovSmolensky, see for example AroraBarak Part II chapter 13, section
13.2).
 Natural properties and the RazborovRudich 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 AroraBarak, 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 MAX3SAT has a a 7/8
approximation algorithm when all 3 literals are different).
 The problem maxqCSP.
 Relationship between PCP and hardness of approximation:
MaxqCSP 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 CookLevin
theorem and intuitive connection to errorcorrecting codes.