Algebra and Computation

Course number: 6.885
Prereq: 6.840 + 6.046 + 18.703.
Time: MW 11:00-12:30pm
Location: 36-155
3-0-9 H-Level Grad Credit
Instructor: Madhu Sudan
Homepage: http://theory.csail.mit.edu/~madhu/FT05/

Bulletin Board
1. Sign up for scribing. Send email volunteering for specific dates. See scribes.txt for
availability.
2. Here's feedback on lecture 4.

3. Problem set (tex, ps, pdf) out now. Due Monday, November 14, 2005

Course announcement

Tentative schedule of topics: (to be added)

Lecture 01 (09/07): Administrivia, Course Contents. Notes (tex, ps, pdf).
Lecture 02 (09/12): Review of algebra: Groups, Rings, Fields. Integral domains, Factorization Domains. Notes (tex, ps, pdf).
Lecture 03 (09/14): Unique Factorization Domains, Gauss's Lemma. Finite fields and their existence. Notes (tex, ps, pdf).
Monday (09/19): Student holiday - no classes.
Lecture 04 (09/21): Membership in permutation groups. Prenotes (tex, ps, pdf). Notes (tex, ps, pdf). Feedback from the class.
Lecture 05 (09/26): Finding roots of univariate polynomials over finite fields of odd characteristic. Notes (tex, ps, pdf).
Lecture 06 (09/28): Towards factorization of higher degree polynomials: Review of polynomials. Notes (tex, ps, pdf).
Lecture 07 (10/03): Factorization of polynomials over finite fields. Notes (tex, ps, pdf).
Lecture 08 (10/05): Towards factoring of multivariate polynomials and polynomials over rationals. Hensel Lifting. Notes (tex, ps, pdf).
Monday (10/10): Columbus Day Holiday.
Lecture 09 (10/12): Factorization of bivariate polynomials. Resultants. Degree bound on the resultant. Notes (tex, ps, pdf).
Lecture 10 (10/17): Factorization of bivariate polynomials - conclusion. Start factoring polynomials over rationals. Notes (tex, ps, pdf).
Lecture 11 (10/19): Lattices and algorithmic problems. Finding short vectors (the LLL algorithm). Notes (tex, ps, pdf).
Lecture 12 (10/24): CANCELLED DUE TO FOCS.
Lecture 13 (10/26): Conclusion of the LLL algorithm. Conclusion of factoring of polynomials over the rationals. Many exercises. Notes (tex, ps, pdf).
Lecture 14 (10/31): Primality Testing - 1. Notes (tex, ps, pdf).
Lecture 15 (11/02): Primality Testing - 2. Notes (tex, ps, pdf).
Lecture 16 (11/07): Applications of factorization in decoding of error-correcting codes. Notes (tex, ps, pdf).
Lecture 17 (11/09): The Ideal Membership Problem. Groebner bases. Notes (tex, ps, pdf).
Lecture 18 (11/14): Groebner bases (contd.). Notes (tex, ps, pdf).
Lecture 19 (11/16): Complexity of Ideal Membership. Notes (tex, ps, pdf).
Lecture 20 (11/21): Hilbert's Nullstellensatz. Notes (tex, ps, pdf).
Lecture 21 (11/23): Quantifier Elimination. Notes (tex, ps, pdf).
(11/24-11/25): Thanksgiving.
Lecture 22 (11/28): Algebraic computation models. Some lower bound techniques. Notes (tex, ps, pdf).
Lecture 23 (11/30): Lower bound for multi-point polynomial evaluation; Bezout's Theorem. Notes (tex, ps, pdf).
Lecture 24 (12/05): TBA
Lecture 25 (12/07): Guest Lecture in 32-G575 by Joel Friedman.
Lecture 26 (12/12): TBA
Lecture 27 (12/14): TBA

References

For the time being, we'll use scribe notes from the last time the course was taught as the references. The full set of notes is here. The course website is here.
Over time, we'll add others.

For scribes, here is a sample file and the preamble.tex file that it uses.