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] |
Return to
CPS240 Homepage