## 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).

## Administrivia:

Credit:1 hourCourse work:Several problem sets, probably a take-home final examPrerequisites:CS 373 or CS 375 or my permission. Algorithmically and/or mathematically mature undergraduates are welcome.Will this satisfy the graduate theory course requirement?Only if you are a theory student. If you think this applies to you, talk to me in person.## Possible course topics:

Decision trees:searching, sorting, and selection; evasiveness of string and graph properties; deterministic vs. randomized (vs. quantum?) complexityRange searching models:pointer machines; indexability; semigroup and group arithmeticAlgebraic complexity:straight-line programs; branching programs; algebraic decision and computation trees; pebbling games; space/time tradeoffsCircuit complexity:lower bounds for monotone circuits; size/depth/fan-in tradeoffsSorting networks:expanders; the AKS networkCommunication complexity:two-party and multi-party protocols; VLSI area/time tradeoffsReal-number computing:real RAMs; the Blum-Shub-Smale modelQuantum computing:Grover and Shor's algorithms; quantum circuits and decision trees## Suggested reading:

(This list will expand as the course progresses.)

Recommended textbook:John E. Savage. Models of Computation: Exploring the Power of Computing. Addison-Wesley, 1998. See also Savage's complexity course at Brown.

- Pankaj K. Agarwal and Jeff Erickson. Geometric range searching and its relatives. Advances in Discrete and Computational Geometry, pages 1-56. AMS Press, 1999.
- Bernard Chazelle. The Discrepancy Method: Randomness and Complexity. Cambridge University Press, 2001.
- Catherine E. Chronaki. A survey of evasiveness: Lower bounds on the decision-tree complexity of Boolean functions, Technical Report, Computer Science Department, University of Rochester, 1990.
- László Lovasz and Neal E. Young. Lecture notes on evasiveness of graph properties. Technical Report CS-TR-317-91, Computer Science Department, Princeton University, 1991. ArXiv:cs.CC/0205031.
- Jiri Matousek. Lectures on Discrete Geometry. Springer-Verlag, 2002.