Algebra and Computation
Course announcement
Lecture notes
The lecture notes for the class are available either individually
(below) or as one
ps file (1.3 M)
or as a
gzipped ps file (412 K).
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 .