Lectures

1: Wednesday, August 25 2010 (Guest lecturer: Peter Bro Miltersen)

Time Complexity.
The sequential Turing machine model. Time complexity. A time lower bound using crossing sequences. Universal Turing machines. Tape reduction.

Suggested reading materials:

Chapter 10 of Formal languages and their relation to automata by John E. Hopcroft Jeffrey D. Ullman (direct link).

2: Friday, August 27 2010 (Guest lecturer: Peter Bro Miltersen)

Tape reduction and Time Hierarchy.
Tape reduction. Time hierarchy theorem. P and EXP. Nondeterministic Turing machines.

Suggested reading materials:

Chapter 10 of Hopcroft & Ullman.

3: Wednesday, September 1 2010

Nondeterminism and Space Complexity.
Nondeterministic time hierarchy theorem. NP and NEXP. Space Complexity. A space lower bound using crossing sequences.

Suggested reading materials:

Chapter 10 of Hopcroft & Ullman.
Arora&Barak, Theorem 3.2

4: Friday, September 3 2010

Space and Time.
How to halt a space bounded Turing machine. Space hierarchy Theorem. L, NL and PSPACE. Relationships between space and time complexity. The reachability method. Savitch' Theorem.

Suggested reading materials:

Arora&Barak, pp 78 - 83 top, pp 85 bottom - 86 mid.

5: Wednesday, September 8 2010

Logspace reductions and completeness.
Logspace reductions. STCON is complete for NL. CVP is complete for P. Circuit SAT is complete for NP. The Immerman-Szelepcsenyi theorem.

Suggested reading materials:

Arora&Barak, pp 82, pp 106 - 111 mid, pp 87 bottom - 92.

6: Friday, September 10 2010

Alternation.
Logspace uniform circuit characterization of P. Alternating Turing Machines.

Suggested reading materials:

Arora&Barak, pp 111 mid - 112.
Alternation by Chandra, Kozen and Stockmeyer (original paper), pp 114 - 127 mid.

7: Wednesday, September 15 2010

Polynomial time hierarchy.
The Polynomial Time Hierarchy. Oracle Turing machines. Oracle definition of PH. Complete problems for levels of PH. 2-Color Extension is Π^p₂ complete.

Suggested reading materials:

Arora&Barak, pp 95 - 100, pp 83 - 85, pp 102 mid - 103.
Recap reduction from CircuitSAT to NAESAT and from NAESAT to 3COL.

8: Friday, September 17 2010

Randomized computation.
Complete problems for PSPACE: TQBF and Generalized Geography. Probabilistic Turing Machines. Schwartz-Zippel lemma. Arithmetic Circuit Identity Testing. Classes BPP, RP, ZPP. Amplification.

Suggested reading materials:

Arora&Barak, pp 123 - 136.

9: Wednesday, September 22 2010

Connecting PH, P/poly and BPP.
Collapses of PH. Karp-Lipton. Meyer's Theorem. BPP ⊆ P/poly. BPP ⊆ PH.

Suggested reading materials:

Arora&Barak, pp 97 - 98, pp 113 bottom - 115 top, pp 135 mid - pp 137.

10: Friday, September 24 2010

Counting complexity.
Padding. The counting class #P. #SAT and Permanent are complete for #P.

Suggested reading materials:

Arora&Barak, pp 341 - 351 mid.

11: Wednesday, September 29 2010

Valiant-Vazirani and Toda's Theorem.
Randomized reductions. Valiant-Vazirani Theorem. The class ⊕P. First half of Toda's Theorem.

Suggested reading materials:

Arora&Barak, pp 352 mid - 357.

12: Friday, October 1 2010

Toda's Theorem. Parallel Computation and Circuits.
Second half of Toda's Theorem. Shannon's counting lower bound for circuits. Parallel Computation. The NC hierarchy.

Suggested reading materials:

Arora&Barak, pp 357 - 358.
Arora&Barak, pp 115 - 119 mid.

13: Wednesday, October 6 2010

Basic circuit constructions.
Placing L and NL in the NC hierarchy: U_L-NC¹ ⊆ L and NL ⊆ U_L-AC¹. ADDITION in AC⁰. The class circuit TC⁰. MULTIPLICATION in TC⁰.

Suggested reading materials:

Heribert Vollmer, "Introduction to Circuit Complexity", pp 5 - pp 21.

14: Friday, October 8 2010

Razborov-Smolensky Circuit Lower Bound.
The circuit classes AC⁰[m] and ACC⁰. Probabilistic polynomials. The Razborov-Smolensky lower bound.

Suggested reading materials:

Arora&Barak, pp 291 - 293.

Quarter break

15: Friday, October 29 3 2010

Circuits and Branching Programs
Exponential lower bound for depth two TC⁰ circuits. Branching programs and space.

Suggested reading materials:

Threshold circuits of bounded depth by Hajnal, Maass, Pudlák, Szegedy and Turán (original paper), pp 134-137(mid).
Arora&Barak, pp 275(mid) - 276(mid), 300.

16: Wednesday, November 3 2010

Barrington's Theorem.
Permutation Branching programs. Barrington's theorem. MOD₃ o MOD₂ circuits.

Suggested reading materials:

Bounded-width polynomial-size branching programs recognize exactly those languages in NC¹ by Barrington (original paper), pp 150-154(mid).
Width-3 permutation branching programs by Barrington (original paper).

17: Friday, November 5 2010

Interactive Proofs.
Interactive proof for #SAT_D, SUMCHECK protocol. IP ⊆ PSPACE.

Suggested reading materials:

Arora&Barak, pp 143 - 150, 157-160

18: Wednesday, November 10 2010

IP=PSPACE. Arthur-Merlin Games
Interactive proof for TQBF. IP=PSPACE. Public coins and AM.

Suggested reading materials:

Arora&Barak, pp 161 - 162, 150-157

19: Friday, November 12 2010

Expander Graphs
Spectral and edge expansion. Expander mixing lemma. Deterministic error reduction. Randomness-efficient error reduction.

Suggested reading materials:

Arora&Barak, pp 421-424, 426(mid)-429, 431(mid)-433

20: Wednesday, November 17 2010

Error reduction and derandomization
Deterministic and randomness-efficient error reduction using expander graphs: proofs. Derandomization using Pseudo-random generators.

Suggested reading materials:

Arora&Barak, pp 431(mid)-433
Arora&Barak, pp 176(bottom)-182

Friday, November 19 2010

No lecture.

21: Wednesday, November 24 2010

Derandomization using PRG's
Derandomization using Pseudo-random generators. Hardness vs. Randomness. Unpredictability implies pseudorandomness.

Suggested reading materials:

Arora&Barak, pp 402-408
Arora&Barak, pp 181-182

22: Friday, November 26 2010

Nisan-Wigderson PRG
The Nisan-Wigderson pseudo random generator construction.

Suggested reading materials:

Arora&Barak, pp 410-413(mid)

23: Wednesday, December 1 2010

Hardness Amplification
Hardness amplification. Error correcting codes. Locally decodable codes. List decodable codes.

Suggested reading materials:

Arora&Barak, pp 379(bottom)-398 (read as overview)

24: Friday, December 3 2010

Probabilistically Checkable Proofs.
Probabilistically Checkable Proofs. Hardness of approximation. Gap version of constraint satisfaction problems. QUADEQ is NP-complete.

Suggested reading materials:

Arora&Barak, pp 237-246, 249-251

25: Wednesday, December 8 2010

PCP based on Linearity Testing.
Probabilistically Linearity Testing. PCP from the Walsh-Hadamard code: NP ⊆ PCP(n^O(1),O(1)).

Suggested reading materials:

Arora&Barak, pp 475(mid)-479, 249-253

26: Friday, December 10 2010

PCP: Overview, degree reduction and alphabet reduction.
Overview of proof of PCP Theorem. Degree reduction using expander graphs. Start on Alphabet reduction using PCP's of proximity.

Suggested reading materials:

Arora&Barak, pp 460-463, 491(mid)-493(mid), 470(mid)-472

27: Wednesday, December 15 2010

PCP: Alphabet reduction and Gap amplification.
Alphabet reduction using PCP's of proximity. Gap amplification by random walks. Conclusion of course and talk about exam.

Suggested reading materials:

Arora&Barak, pp 470(mid)-472, 464(bottom)-470(mid)

CT10

Lectures