Properties of GapP
Scribe Notes by Madhav Suresh
Friday, March 30, 2012
Wednesday, March 28, 2012
Monday, March 26, 2012
Lecture 1
Definition and Properties of #P
Scribe Notes by George Askalidis
L. Fortnow. Counting complexity. In L. Hemaspaandra and A. Selman, editors, Complexity Theory Retrospective II, pages 81-107. Springer, 1997.
S. Fenner, L. Fortnow, and L. Li. Gap-definability as a closure property. Information and Computation, 130(1):1-17, 1996.
Scribe Notes by George Askalidis
L. Fortnow. Counting complexity. In L. Hemaspaandra and A. Selman, editors, Complexity Theory Retrospective II, pages 81-107. Springer, 1997.
S. Fenner, L. Fortnow, and L. Li. Gap-definability as a closure property. Information and Computation, 130(1):1-17, 1996.
Thursday, February 2, 2012
Course Information
Spring 2012
This course will cover a variety of topics in computational complexity including pseudorandomness, counting complexity, quantum computing and the structure of complete sets.
Prerequisite: EECS 335 or equivalent
There will be no textbook for the course. This blog will link to papers and scribe notes.
There will be no textbook for the course. This blog will link to papers and scribe notes.
Grading will be based on scribe notes and a presentation of a recent paper in computational complexity.
Subscribe to:
Posts (Atom)