Algebra and Computation
Preliminary course announcement
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
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.