Algebra and Computation
Preliminary course announcement
Number: 6.966
Title: Algebra and Complexity Theory
Instructor: Madhu Sudan
Meets: 2:304:00pm, MW in 34302.
Prereq: Undergraduate courses in
 Complexity theory (6.045) and
 Discrete Math. (6.042) or Algebra (3.1415)
309 GLevel Grad Credit
This course studies the interplay between algebra
and computation. The course will be divided into
roughly three equal parts (1 <= #lectures/part <= 24).
 Algorithms for fundamental algebraic problems:


Factorization of polynomials:
 Over reals, finite fields, integers;
 For univariate and multivariate case;
 Application to encoding+decoding errorcorrecting
codes

Quantifier elimination: How to solve systems of
polynomial equations. Application to kinematics
and robot motion planning

Uniform models of algebraic computation.

 Algebraic versions of the P=NP? question.
 Its relationship to the classical question.
 Complexity of the ``Hilbert's Nullstellensatz''.
 Role of quantifier elimination.

Nonuniform models of algebraic computation.

 Algebraic decision trees, branching programs, PRAM.
 Lower bounds in these models.