MIT Department of Electrical Engineering & Computer Science

EECS Fall 1998 Catalogue Supplement

6.966 Algebra and Complexity Theory

MW 2:30-4, 34-302
Prof. Madhu Sudan, NE43-307, x9680
Prerequisite: 6.042J, 6.045J
3-0-9

Studies the interplay between algebra and computation.

Topics:

Algorithms for fundamental algebraic problems;
Factorization of polynomials, Quantifier elimination;
Uniform models of algebraic computation;
Algebraic versions of the P=NP? question and their relationship to the classical question;
complexity of the "Hilbert's Nullstellensatz;"
non-uniform models: algebraic decision trees, branching programs, PRAM and lower bounds in these models.