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:

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