Algebra and Computation

Preliminary course announcement

Number: 6.966
Title: Algebra and Complexity Theory
Instructor: Madhu Sudan
Meets: 2:30-4:00pm, MW in 34-302.

Prereq: Undergraduate courses in

• Complexity theory (6.045) and
• Discrete Math. (6.042) or Algebra (3.1415)

3-0-9 G-Level 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 error-correcting 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.

Non-uniform models of algebraic computation.

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