CSCI 8610 - Topics in Theoretical Computer Science

Instructor: E. Rodney Canfield

Fall

Course Information:

This is an advanced topics course in the Theory of Computation. Students taking the course have had the equivalent of both CSCI 2670 and CSCI 6610 before.

Topics vary with offering, typically reflecting research interests of the instructor. Research papers are used in lieu of a text. Students are required to make an extended presentation (3-5 lectures) on an assigned paper.

Fall, 2003: We used the text "Computational Complexity" by Papadimitriou as a sourcebook.

Fall, 2004: We are using research papers and tracts for the course. Examples:

1. Doug Wiedemann, Solving sparse linear equations over finite fields.
2. J. De'nes, A. D. Keedwell, Latin squares and their applications.
3. Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf, Quantum Lower Bounds by Polynomials.
4. Noam Nisan and Mario Szegedy, On the degree of boolean functions as real polynomial.
5. Richard Beigel, The Polynomial Method in Circuit Complexity.
6. Victor Shoup, A Computational Introduction to Number Theory and Algebra,
7. Robert J. McEliece, Finite Fields for Computer Scientists and Engineers.
8. Donald E. Knuth, The Art of Computer Programming, volume II.
9. E. R. Berlekamp, Algebraic Coding Theory.