Complexity Theory Fall'01
Week no. 50 (planned)
Lectures
Monday: Towards P vs. NP (combinatorics approach).
Friday: Towards logical independence of P vs. NP (natural proofs).
Week no. 49 (planned)
Lectures
Monday: "The PCP-theorem" (note). Hardness of
Approximations (Arora-Lund).
Friday: Towards P vs. NP (diagonalization approach).
Week no. 48
Lectures
Monday: Kozen, Chapter 16. Friday: "The PCP-theorem" (note).
Week no. 47
Lectures
Monday: Miltersen, Section 5.3. Friday: Kozen, Chapter 15.
Week no. 46
Lectures
Miltersen, Section 4.3, Section 5(.0), Section 5.2
- Trevisan's extractor - conclusion.
- Pseudorandom generators and hitting set
generators.
- Sipser's hitting set generator
Homework (due December 3)
Week no. 45
Lectures
Miltersen, Section 3.2, 2.3 and 4.3.
- Extractors. Statistical distance and min-entropy.
- Error correcting codes. The Reed-Solomon code and
the Hadamard code.
- Trevisan's extractor.
Week no. 44
Lectures
Miltersen, Section 2.1, 3.1, and 4.1.
- BPP is in P/poly
- pBPP = pRP[pRP].
- Dispersers. Expander-based dispersers.
Week no. 43
Lectures
- The classes RP, BPP and pBPP. Kozen
chapters 13, 14 and Miltersen, Section 2.1.
Homework (due November 9)
Week no. 42
Lectures
Homework (due October 26)
- HW4.1, HW4.2, HW5.1, HW6.2, HW6.3 in Kozen
Week no. 41
Lectures
- Alternation (Kozen 7)
- QBF and Generalized Geography are complete for PSPACE (Kozen 8)
- The Polynomial-Time Hierarchy (Kozen 9)
- The use of oracles to separate P and NP (Kozen 27)
Week no. 40
Lectures
- DTIME(T(n)) is contained in DSPACE(T(n)/log(T(n))) ("Space is better than time" -handout)
Homework (due October 12)
Week no. 39
Lectures
- Boolean Circuits
- CIRCUIT VALUE PROBLEM complete for P (Kozen 6)
- CIRCUIT SAT PROBLEM complete for NP
- Cook's theorem
- Circuits as a model of computation. PSIZE
- Turing machines that take advice. P/poly
- PSIZE=P/poly
- Logspace uniformity of Circuit fmilies
Week no. 38
Lectures
- Time Hierarchy theorem. Padding technique (Kozen 3)
- The Immerman/Szelepcsényi Theorem (Kozen 4)
- Logspace reductions (Kozen 5)
- GRAPH ACCESSIBILITY PROBLEM (MAZE) complete for NL
Homework (due September 28)
Week no. 37
Lectures
- Time and Space Complexity Classes (Kozen 2)
- Savitch's Theorem (Kozen 2)
- Robustness of Complexity classes
- Space hierarchy theorem (Kozen 3)
Week no. 36
Lectures
- Regularity: Kleenes Theorem, 2-way FA's (Papa 2.8.12)
- Crossing Sequences (Kozen 1)
Homework (due September 14)
- 2.8.13, 2.8.17, and 3.4.2 in Papa
- HW 1.1 in Kozen
Description of Course
The first half of the course will mainly be based on
- Papadimitriou: Computational Complexity, Addison Wesley, 1994 (Papa)
- Dexter Kozen: Lectures on the Theory of Computing, Cornell University (Kozen)
Homework is due on the Friday of every week with an odd number, starting with week no 37. Course credit (2 points) will be given for satisfactory answers to the homework.
There will be an average of three hours of lecturing per week. In "even" weeks one of the lecture hours on Friday will be used for discussing the homework.
Most recently modified on 2001/9/3
Erik Meineche Schmidt
ems@brics.dk