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.