CPS 240: Computational Complexity

Computational complexity formally characterizes the complexity of solving problems using a computer (i.e., computational efficiency). It is remarkable that despite the plethora of computational devices available, there is a "grand unifying theory" which characterizes computational efficiency. This graduate-level course will provide you with the basic knowledge of this field. In the first half of the course, we will cover the basic computational models and their interrelationships, followed by the various fundamental complexity classes. In the second half of the course, we will cover advanced topics of pseudorandomness, cryptography, interactive proofs, and the PCP theorem, which have had fundamental impact on several disciplines such as computer security, data-stream computation, and approximation algorithms.You need CPS130 or equivalent as prerequisite.

Course Materials: I will follow the preprint of a yet to be published book, "Computational Complexity: A Modern Approach" by Sanjeev Arora and Boaz Barak. I will keep a few copies of this book in an easily accessible place. Most of this material can also be found in the book [Pap] listed below; however, I prefer the ordering of the material in Arora's book. There are many great lecture notes available on the web for most of the course material. Please search on the web for "Laszlo Lovasz", "Martin Tompa", or "Sanjeev Arora" for some eminently readable notes.

Assignments:
    1/31: Homework 1    (Due 2/10)
    2/22: Homework 2    (Due 3/3)
    4/09: Homework 3    (Due 4/21)
     4/09: Homework 4    (Due 4/28)
     4/28: Final Exam    (Due 4/29, 4pm)

Timing:
Lectures:           Tue-Thu, 2:50-4:05   (D243)
Office Hours:          Wed, 1:30-3:30   (D205)

Grading: There will be 4 homeworks (50%), a midterm (20%) and an end-term (30%).
This course satisfies the Algorithms qualifier requirement.

Lect.	Date	Topics	Handouts	Reading
1	Jan. 13	Introduction, Turing Machines, Non-Determinism, Church Turing Hypothesis		[HMU, Ch 8]
2	Jan. 18	P, NP, NP-Completeness Cook-Lewin Theorem and 3SAT		[Pap, Ch9] [HMU, Ch10]
3	Jan. 20, 27	NP-Completeness via Reductions coNP, EXPTIME, NEXPTIME		[GJ, Ch3,4] [Pap, Ch9] [HMU, Ch10]
	Jan. 25	No Class - SODA 2005
5	Feb. 1,3	Space Complexity PSPACE Completeness and TQBF Examples of PSPACE Complete Problems	HW1	[Pap, Ch19] [HMU, Ch11]
7	Feb. 8	L, NL, Logspace Reductions PATH is NL-Complete		[Pap, Ch7,16]
8	Feb. 10	PSPACE=NPSPACE [Savitch 1970] NSPACE=coNSPACE		[Pap, Ch7]
9	Feb. 15	Diagonalization Time-Space Hierarchy Theorems		[Pap, Ch7,8]
10	Feb. 17	Relativized Proof Techniques Oracle Turing Machines P versus NP via Diagonalization?		[Pap, Ch14]
11	Feb. 22	Polynomial Hierarchy (PH) Properties of PH Oracle Characterization of PH	HW2	[Pap, Sec16.2] [CKS]
12	Feb. 24	Circuit Complexity, P/poly, Logspace uniform classes		[Pap, Ch11]
13	Mar. 1	Can P/poly resolve P versus NP? Parallel Computation		[Pap, Ch11]
14	Mar. 3	Log-depth Circuits, NC Relation of NC to Parallel Computing P-Completeness and Linear Programming		[Pap, Ch11]
15	Mar. 8	Randomized Complexity: RP, BPP, ZPP Examples of PTMs		[Pap, Ch11] [HMU, Ch11]
16	Mar. 10	Mid-Term Exam
	Mar. 15,17	No Class - SPRING BREAK
17	Mar. 22	Proof of the Schwartz-Zippel Lemma Relation of BPP to PH and P/poly
18	Mar. 24	Trapdoor Functions, Cryptography RSA and Discrete Log Cryptosystems		[Pap, Ch18]
19	Mar. 29	One Way Functions: Discrete Log Pseudorandomness: Two equivalent definitions		[Pap, Ch11]
20	Mar. 31	Goldreich-Levin Hardcore Bit, and Pseudorandom Number Generators
	Apr. 5,7	No Class - ICDE 2005
21	Apr. 12	Interactive Proofs (IP) Zero Knowledge Proofs Public Randomness and the class AM	HW3 HW4	[Pap, Ch19]
22	Apr. 14	IP = PSPACE		[Pap, Ch19]
23	Apr. 19	IP = PSPACE (contd.) Program Checking Multiprover Interactive Proofs (MIP)		[Pap, Ch19]
24	Apr. 21	Relation between MIP and Proof Verification History of the PCP Theorems Hardness of Approximating MAX-SAT
25	Apr. 26, 28	NP in PCP(poly(n),1)
27	Apr. 28-29	End-Term Exam (Take Home)

Lect.

Date

Topics

Handouts

Reading

Jan. 13

Introduction, Turing Machines,
Non-Determinism,
Church Turing Hypothesis

[HMU, Ch 8]

Jan. 18

P, NP, NP-Completeness
Cook-Lewin Theorem and 3SAT

[Pap, Ch9]
[HMU, Ch10]

Jan. 20, 27

NP-Completeness via Reductions
coNP, EXPTIME, NEXPTIME

[GJ, Ch3,4]
[Pap, Ch9]
[HMU, Ch10]

Jan. 25

No Class - SODA 2005

Feb. 1,3

Space Complexity
PSPACE Completeness and TQBF
Examples of PSPACE Complete Problems

HW1

[Pap, Ch19]
[HMU, Ch11]

Feb. 8

L, NL, Logspace Reductions
PATH is NL-Complete

[Pap, Ch7,16]

Feb. 10

PSPACE=NPSPACE [Savitch 1970]
NSPACE=coNSPACE

[Pap, Ch7]

Feb. 15

Diagonalization
Time-Space Hierarchy Theorems

[Pap, Ch7,8]

Feb. 17

Relativized Proof Techniques
Oracle Turing Machines
P versus NP via Diagonalization?

[Pap, Ch14]

Feb. 22

Polynomial Hierarchy (PH)
Properties of PH
Oracle Characterization of PH

HW2

[Pap, Sec16.2]
[CKS]

Feb. 24

Circuit Complexity,
P/poly, Logspace uniform classes

[Pap, Ch11]

Mar. 1

Can P/poly resolve P versus NP?
Parallel Computation

[Pap, Ch11]

Mar. 3

Log-depth Circuits, NC
Relation of NC to Parallel Computing
P-Completeness and Linear Programming

[Pap, Ch11]

Mar. 8

Randomized Complexity: RP, BPP, ZPP
Examples of PTMs

[Pap, Ch11]
[HMU, Ch11]

Mar. 10

Mid-Term Exam

Mar. 15,17

No Class - SPRING BREAK

Mar. 22

Proof of the Schwartz-Zippel Lemma
Relation of BPP to PH and P/poly

Mar. 24

Trapdoor Functions, Cryptography
RSA and Discrete Log Cryptosystems

[Pap, Ch18]

Mar. 29

One Way Functions: Discrete Log
Pseudorandomness: Two equivalent definitions

[Pap, Ch11]

Mar. 31

Goldreich-Levin Hardcore Bit, and
Pseudorandom Number Generators

Apr. 5,7

No Class - ICDE 2005

Apr. 12

Interactive Proofs (IP)
Zero Knowledge Proofs
Public Randomness and the class AM

HW3
HW4

[Pap, Ch19]

Apr. 14

IP = PSPACE

[Pap, Ch19]

Apr. 19

IP = PSPACE (contd.)
Program Checking
Multiprover Interactive Proofs (MIP)

[Pap, Ch19]

Apr. 21

Relation between MIP and Proof Verification
History of the PCP Theorems
Hardness of Approximating MAX-SAT

Apr. 26, 28

NP in PCP(poly(n),1)

Apr. 28-29

End-Term Exam (Take Home)

CPS 240: Computational Complexity

Relevant References

Books on Complexity Theory

History of Computing and Complexity Theory

Turing Machines

Complexity Theory: Early Papers

Reducibilities

IP

PCP