Madhu Sudan: Algebra and Computation
Course announcement
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.
Lecture notes
The lecture notes for the class are available either individually (below) or as one pdf file (1.3 M) .
Topics covered
- Lecture 1: Overview; Preliminaries.
- Lecture 2: Polynomials; The factorization and GCD problems.
- Lecture 3: Polynomials and error-correcting codes. The Euclidean algorithm for GCD. Applications. Resultant.
- Lecture 4: Properties of the resultant. Applications. Towards factorization of polynomials: Finding square roots modulo a prime.
- Lecture 5: Factorization of univariate polynomials over finite fields.
- Lecture 6: Berlekamp’s deterministic algorithm for factoring univariate polynomials. Existence, density and properties of irreducible polynomials.
- Lecture 7: Factoring bivariate polynomials. Hensel’s lifting.
- Lecture 8: Factoring bivariate polynomials (contd.). Digression: Applications to error-correction algorithms.
- Lecture 9: Irreducibility testing; Black-box factoring of multivariate polynomials.
- Lecture 10: Factoring polynomials over the rationals; Reduction to basis reduction.
- Lecture 11: LLL’s Basis reduction algorithm.
- Lecture 12: (2nd Phase of course) Ideals and Varieties. Division in Ideals; Groebner bases.
- Lecture 13: Construction and uniqueness of Groebner bases. Solution to the Ideal Membership problem.
- Lecture 14: Upper bound on the degrees for ideal generation. Complexity lower bound.
- Lecture 15: Varieties. Emptiness of a variety. Elimination. Hilbert’s Nullstellensatz.
- Lecture 16: Strong form of Hilbert’s Nullstellensatz. Quantifier Elimination.
- Lecture 17: Quantifier elimination (contd.); Bezout’s Thm.
- Lecture 18: Bezout’s Thm. and some applications.
- Lecture 19: Algebraic models of computation; Ben-Or Cleve result.
- Lecture 20: Blum-Shub-Smale model of computation (contd.) Undecidability of Mandelbrot Set.
- Lecture 21: Algebaic settings for the P=NP question
- Lecture 22: An Arthur-Merlin proof for the Hilbert’s Nullstellensatz.
- Lecture 23: Non-uniform lower bounds; Linear independence; algebraic independence; Strassen’s degree bound.
- Lecture 24: Ben-Or’s lower bounds based on no. of connected components; Survey of other methods: Volume; Euler characteristic and Betti numbers.
- Lecture 25: Mulmuley’s Algebraic PRAM without bit operations. Lower bounds for LP and Max Flow.
- Lecture 26: Summary. What we didn’t cover …
Style files for scribes: sample.tex and preamble.tex.