Math 8815: Complexity Theory Fall 2007
Ulam Seminar, Department of Mathematics,
University of Colorado at Boulder
- Speaker: Michael Soltys, email:
“my last name at mcmaster.ca”
- Time and place: Wednesdays at 3:00 in ECCR
116.
- Outline
Announcements:
- Nov 28: Chapter 6 with revisions, as well as chapter 7
(randomized classes), are posted below.
- Oct 30: Chapter 5 (Circuits) has been posted below.
- Oct 11: New version of chapter 3 has been posted, with a solution
to exercise 3.3.4, which shows how to put QBF in normal form. Chapter
4 has been posted as well.
- Sept 26: Chapter 3 and a new version of chapter 2 have been
posted below.
- Sept 19: A revised version of chapter 2 has been posted below.
- Sept 13: Chapter 2 has been posted below (and a small
bibliography).
- Sept 6: Berkowitz's Algorithm:
- Here is the paper containing the material presented on Sept 5th:
Berkowitz's algorithm and clow
sequences, Michael Soltys, ELA, Volume 9, pp. 42-54, April
2002.
- The original paper of Berkowitz is:
On computing the determinant in small parallel time using a small
number of processors, Stuart J. Berkowitz, Information Processing
Letters, 18:147-150, 1984.
- For clow sequences:
Determinant: Combinatorics, algorithms, and complexity, Meena
Mahajan and V. Vinay, Chicago Journal of Theoretical Computer Science,
vol. 1997, article 5, 1997.
- Aug 23: Organizational meeting: Wednesday, August 29, at 3pm, in
ECCR 116.
Notes:
The seminar will be based on my notes which I am currently
transforming into a book.