Server: Netscape-Commerce/1.12 Date: Wednesday, 20-Nov-96 22:45:04 GMT Last-modified: Friday, 27-Jan-95 20:56:13 GMT Content-length: 851 Content-type: text/html
Uses of Randomness in Complexity Theory - Spring 95

Uses of Randomness in Complexity Theory

Techniques involving randomness have played a crucial role in complexity theory over the past decade. They have been used to prove results that seemingly did not call for them, such as Toda's theorem, and the fact that many NP-hard problems are also NP-hard to approximate.

The course will survey these developments, at the same time putting them in context by also covering ideas from cryptography, interactive proofs, and program checking that led to them.

The course is scheduled for Tu-Thurs from 10:30 to 12, but that could change if many people have conflicts with that.

Prerequisites: Solid Knowledge of NP-completeness and reductions. Some mathematical maturity.