# 198:538: Complexity of Computation

Notes for the Spring, 1998 version of the class are now becoming
available. Additional notes will be appearing here.
- January 26, 1998.

(Preliminaries, and the Gap Theorem.)

Notes by Sunny Daniels.
- January 28, 1998.

(The Almost-Everywhere Hierarchy Theorems for Space and Time.)

Notes by Norbert Lis.
- February 2, 1998.

(The Speed-Up Theorem -- also known as the Blum Speed-Up Theorem.)

Notes by Takahiro Murata.
- February 4, 1998.

(The Nondeterministic Time Hierarchy Theorem.)

Notes by Aynur Dayanik.
- February 9, 1998.

(The Translational Method.)

Notes by Zhigang Gu.
- February 11, 1998.

(Nondeterministic Space is Closed under Complement.)

Notes by Yuming Zhang.
- February 16, 1998.

(Alternating Turing Machines.)

Notes by Wen Li.
- February 18, 1998.

(Alternating Turing Machines, continued.)

Notes by Jorge Padilla.
- February 23, 1998.

(Sublinear-time ATMs; Uniform Circuit Complexity.)

Notes by Sunny Daniels.
- February 25, 1998.

(Circuit Complexity Classes.)

Notes by Ali Shokoufandeh.
- February 27, 1998.

(Alternating Turing machines and Circuits.)

Notes by Takahiro Murata.
- March 9 and 11 1998.

(Barrington's Theorem, and Reducibility and Completeness.)

Notes by Norbert Lis.
- March 13, 1998.

(Classes of Languages and Functions. Turing Reducibility)

Notes by Zhigang Gu.
- March 23 and 25, 1998.

(Ladner's Theorem and Related Topics.)

Notes by Wen Li.
- March 30, 1998.

(Primes and Factoring are in UP.)

Notes by Aynur Dayanik.
- April 1, 1998.

(NP in P/poly implies PH collapses.)

Notes by Jorge Padilla.
- April 6, 1998.

(Sets that require large circuits. Intro to Probabilistic Classes.)

Notes by Yuming Zhang.
- April 8 and 13, 1998.

(BPP is in PH (using pseudorandom generators).)

Notes by Marti Sanchez.
- April 14, 1998.

(The Block Design construction for the NW-Generator.)

Notes by Sunny Daniels.
- April 20 and 22, 1998.

(Toda's Theorem.)

Notes by Takahiro Murata.
- April 27, 1998.

(End of Toda's Theorem; Oracles.)

Notes by Wen Li.
- April 29, 1998.

(Intro to Interactive Proofs)

Notes by Zhigang Gu.
- May 4, 1998.

(Conclusion of IP = PSPACE.)

Notes by Jorge Padilla.