|
|
CT08 / Lectures
- August 27 2008
- Introduction. The sequential Turing machine model. Time
complexity. Simple lower bound using crossing sequences. Tape
reduction. Efficient universal Turing machines. Time hierarchy
theorem.
Suggested reading materials:
- August 29 2008
- Space complexity. Simple lower bound using crossing
sequences. Space hierarchy Theorem. Nondeterministic
complexity. Relationships between space and time complexity. The
reachability method. Savitch' Theorem.
Suggested reading materials:
- Chapter 10 of Formal languages and their relation to automata by John E. Hopcroft Jeffrey D. Ullman.
- Chapter 4 of Complexity Theory:
A Modern Approach by Sanjeev Arora and Boaz Barak. (Skip parts about PSPACE)
- September 3 2008
- Logspace reductions. STCON is complete for NL. CVP is complete for P.
The Immerman-Szelepcsenyi theorem. Nondeterministic space hierarchy theorem.
Suggested reading materials:
- Chapter 4 of Complexity Theory: A Modern Approach by Sanjeev Arora and Boaz Barak. (Skip parts about PSPACE)
- September 5 2008
-
Logspace uniform circuit characterization of P. Circuit SAT is complete for NP.
Alternating Turing Machines. The Polynomial Time Hierarchy.
Suggested reading materials:
- September 10 2008
-
Oracle Turing Machines. Oracle definition of the Polynomial Time Hierarchy.
Complete problems for PSPACE and levels of PH.
Suggested reading materials:
- September 12 2008
-
Time-space lower bounds for SAT. Collapse of PH. Karp-Lipton theorem. Meyer's Theorem. Relativization.
Suggested reading materials:
- September 17 2008
-
No lecture!
I recommend you instead watch the following video-lecture:
Coding Theory: Survey of Recent Progress and Open Questions by Madhu Sudan.
We will use error correcting codes later in this course.
- September 19 2008
-
No lecture!
I recommend you instead watch the following video-lecture:
Discrete Mathematics: Expanders Graphs & Eigenvalues by Nati Linial.
We will use expander graphs later in this course.
- September 24 2008
-
Parallel computation. PRAM's, ATM's and Boolean Circuits. NC and AC hierarchies. ADDITION is in AC0.
Suggested reading materials:
- September 26 2008
-
Threshold Circuits and TC0. TC0 is contained in NC1. MULTIPLICATION is in TC0.
Introduction to the switching lemma and lower bounds for AC0.
Suggested reading materials:
- October 1 2008
-
Proof of the switching lemma and lower bounds for AC0.
Suggested reading materials:
- October 3 2008
-
The Razborov-Smolensky circuit bound. Barrington's Theorem.
Suggested reading materials:
- October 8 2008
-
Randomized Computation. Arithmetic Circuit Identity Testing. Classes BPP, RP, ZPP. Amplification. BPP is in P/poly.
Suggested reading materials:
- October 10 2008
-
BPP is in PH. Randomized logspace. Random walks and USTCON.
Suggested reading materials:
- November 5 2008
- Recap of random walks and USTCON and missing proofs.
Expanders. Error reduction using expanders.
Suggested reading materials:
- November 7 2008
- Error reduction using expanders. Explicit constructions of expanders and USTCON in L.
Suggested reading materials:
- November 12 2008
- Explicit constructions of expanders and USTCON in L. Derandomization using pseudorandom generators.
Suggested reading materials:
- November 14 2008
- Derandomization and the Nisan-Wigderson pseudorandom generator.
Suggested reading materials:
- November 19 2008
- The Nisan-Wigderson pseudorandom generator. Error correcting codes.
Suggested reading materials:
- November 21 2008
- Error correcting codes. Local decoding and hardness amplification.
Suggested reading materials:
- November 26 2008
- Local decoding, list decoding and hardness amplification.
Suggested reading materials:
- November 28 2008
- Interactive proofs. IP=PSPACE.
Suggested reading materials:
- December 3 2008
- Probabilistically Checkable Proofs. NP is in PCP(nO(1),O(1)).
Suggested reading materials:
- December 5 2008
- Linearity Testing. PCP: Overview and degree reduction.
Suggested reading materials:
- December 10 2008
- PCP: Gap amplification.
Suggested reading materials:
- December 12 2008
- PCP: Alphabet reduction. Conclude course and talk about exam.
Suggested reading materials:
|
