Concrete Models of Computation
CS 497 JE: Spring 2003

Jeff Erickson

TuTh 11:00-12:15
256 Mechanical Engineering Building

This course will survey methods for proving that certain computational problems are inherently difficult. Since it is virtually impossible to reason about the difficulty of problems in abstract computing models like Turing machines (hence the whole P vs. NP vs. PSPACE mess), most complexity lower bounds are developed in more restricted models of computation, tailored to the problem at hand. Most of the material will be orthogonal to topics covered in a more traditional abstract computational complexity course (like CS/ECE/Math 479).

Schedule so far:


Possible course topics:

Suggested reading:

(This list will expand as the course progresses.)