CPS 240: Computational Complexity

Lect.	Date	Topics	Handouts	Reading
1	Jan. 9	Introduction, History of computing	Synopsis	[Pap, Ch1]
2	Jan. 16	Turing machines, decidability		[Pap, Ch2] [HU, Ch7]
3	Jan. 21	Turing machine: tape reduction linear speed up		[Pap, Ch2] [HU, Ch12]
4	Jan. 23	Nondeterminism, NTM vs DTM, time complexity, universal TM		[Pap, Ch2,3] [HU, Ch7,12]
5	Jan. 28	Halting problem, computability, primitive recursive function	HW1	[Pap, Ch3] [HU, Ch8]
6	Jan. 30	Complexity measures Space vs time complexity hierarchy theorems		[Pap, Ch7] [HU, Ch12]
7	Feb. 4	Complexity classes, Reachability Savitch's theorem		[Pap, Ch7] [HU,12]
8	Feb 6	Nondeterministic space Reducibilities: many-to-one, truthtable, Turing Oracle TMs		[Pap, Ch7,8] [Pap, Sec14.3]
9	Feb 11	Reducibilities: Examples Relations between reducibilities Transitive and closure properties	HW2	[Pap, Ch8]
10	Feb. 13	Hard and Complete Languages NP-Completeness: Examples and Reductions		[Pap, Ch8,9] [HU, Ch13] [GJ, Ch3]
11	Feb. 18	NP-Completeness: Cook's Theorem Characterizations of NP Co-NP		[Pap, Ch9] [HU, Ch13] [GJ, Ch3,4]
12	Feb. 20	PSPACE: QBF, Motion Planning EXP, NEXP, EXPSPACE First Order Theories	Reducibilities Cook's theorem	[Pap, Ch19] [HU, Ch13]
13	Feb. 25	Alternating TM	[CKS]	[Pap, Sec16.2] [CKS]
14	Feb. 27	Alternating TM Polynomial Hierarchy	HW3	[CKS] [Pap, Ch17]
15	March 4	Polynomial Hierarchy		[Pap, Ch17]
16	March 6	Counting Problems #P		[Pap, Ch18]
	March 11,13	Spring Break
	March 18	Midterm
	March 20,25	Class Cancelled
17	March 27	Circuit complexity, uniform vs nonuniform Lower bounds on size		[Pap, 11.4]
18	April 1	Montone circuits, Razborov's theorem		[Pap, 14.4]
19	April 3	Randomized complexity, Probabilistic TM RP, ZPP, PP, BPP		[Pap, 11]
20	April 8	BPP, circuit complexity, & PH One-way functions, public-key cryptography	HW4	[Pap 11, 17, 18] [Pap 12]
21	April 11	One-way functions, public-key cryptography RSA system Interactive protocols		[Pap 12]
22	April 15	Interactive protocols, IP Intercative protocol for #P IP=PSPACE	[L, Ch3]	[Pap 19] [Handout]
23	April 17	PCP and approximability	[ACGK, Ch6]	[ACGK Ch6]
24	April 22	PCP theorem	[HPS]	[ACGK Ch7] [HPS]

Relevant References

History of Computing and Complexity Theory

S. C. Kleene, Origins of recursive function theory, Annals of the History of Computing, 3 (1981), 52-67.
M. Davis, Why Godel didn't have Church's thesis, Information and Control 54 (1982), 3-24.
J. Hartmanis, Observations about the devlopment of theoretical computer science, Annals of the History of Computing, 3 (1981), 42-51.
M. Sipser, The history and status of the P versus NP question, Proc. 24th Annual ACM Sympos. Theory of Computing, 1992, 603-619.

Turing Machines

J.E. Hopcroft, Turing machines, Scientific American, 250:5 (1984), 86-98.
A. M. Turing, On computable numbers, with an application to the Entscheidungsproblem, Proc. London Math. Scoiety, 2 (1936), 230-265.

Complexity Theory: Early Papers

J. Hartmanis and R. E. Stearns, On the computational complexity of algorithms, Transactions of AMS, 117 (1965), 285-306.
M. Rabin, Degree of difficulty of computing a function and a partial ordering of recursive sets, Tech Rept 2, Hebrew University, 1960.

Reducibilities

R. E. Ladner, On the structure of polynomial time reducibility, J. ACM 22 (1975), 155-171.
R. E. Ladner, N. A. Lynch, and A. L. Selman, A comparison of polynomial time reducibilities, Theoretical Computer Science 1 (1975), 103-123.

First Order Theories

J. Canny, Some algebraic and geometric computations in PSPACE, Proc. 20th Annual ACM Sympos. Theory of Comput., 1988, 460-467.
M. Fischer and M. Rabin, Super-exponential complexity of Persburger arithmetic, in Complexity of Computation, (R. M. Kapr, ed.), SIAM.

Alternation

[CKS] A. Chandra, D. Kozen, and L. Stockmeyer, Alternation, JACM 28 (1981), 114-133.

IP

[BF] L. Babai and L. Fortnow, Arithmetization: A new method in structural complexity theory Comput. Complexity 1 (1991), 41-66.
[L] C. Lund, The Power of Interaction, MIT Press, 1992.

PCP

[ALMSS] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, Proof verification and intractability of approximation problems, J. ACM 45 (1998), 501-555.
[AS] S. Arora and S. Safra, Probabilistic checking of proofs: A new characterization of NP, J. ACM 45 (1998), 70-122.
[H1] J. Hastad, Clique is hard to approximate within n^{1-e}, Acta Math 182 (1999), 105-142.
[H2] J. Hastad, Some optimal inapproximability results, J. ACM 48 (2001), 798-859.
[HPS] S. Hougardy, H.J. Promel, and A. Steger, Probabilistically checkable proofs and their consequences for approximation algorithms, Discrete Math. 136 (1994), 175-223.

Agarwal's Home Page

Return to CPS240 Homepage