Harvard University homepage
HARVARD.EDU

Madhu Sudan: 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/

Style files for scribes: sample.tex and preamble.tex.

Bulletin Board

  • Sign up for scribing. Send email volunteering for specific dates. See scribes.txt for availability.
  • Here’s feedback on lecture 4.
  • Problem set (pdf) out now. Due Monday, November 14, 2005

Course announcement

Course announcement

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

Algebra and Computation

This course studies the interplay between algebra and computation. The course will be divided in two parts.

  • The first part will cover algorithms in Algebra, Number Theory, and Group Theory. Some topics include algorithms for factoring polynomials (Berlekamp,  Lenstra-Lenstra-Lovasz etc.) and algorithms for testing primes (Agarwal-Kayal-Saxena), multiplying matrices (Cohn-Umans), Solving systems of polynomial equations etc.
  • The second part of the course will focus on the interplay between complexity theory and algebra as highlighted by algebraic versions of the P vs. NP question. 

See Algebra and Computation Fall 1998 or notes from an earlier version of this course.

Instructor: Madhu Sudan

Tentative schedule of topics: (to be added)

  • Lecture 01 (09/07): Administrivia, Course Contents. Notes (pdf).
  • Lecture 02 (09/12): Review of algebra: Groups, Rings, Fields. Integral domains, Factorization Domains. Notes (pdf).
  • Lecture 03 (09/14): Unique Factorization Domains, Gauss’s Lemma. Finite fields and their existence. Notes (pdf).
  • Monday (09/19):  Student holiday – no classes.
  • Lecture 04 (09/21): Membership in permutation groups. Prenotes (pdf). Notes (pdf). Feedback from the class.
  • Lecture 05 (09/26): Finding roots of univariate polynomials over finite fields of odd characteristic. Notes (pdf).
  • Lecture 06 (09/28): Towards factorization of higher degree polynomials: Review of polynomials. Notes (pdf).
  • Lecture 07 (10/03): Factorization of polynomials over finite fields.  Notes (pdf).
  • Lecture 08 (10/05): Towards factoring  of multivariate polynomials and polynomials over rationals. Hensel Lifting. Notes (pdf).
  • Monday (10/10): Columbus Day Holiday.
  • Lecture 09 (10/12): Factorization of  bivariate polynomials. Resultants. Degree bound on the resultant. Notes (pdf).
  • Lecture 10 (10/17): Factorization of bivariate polynomials – conclusion. Start factoring polynomials over rationals. Notes (pdf).
  • Lecture 11 (10/19): Lattices and algorithmic problems. Finding short vectors (the LLL algorithm). Notes (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 (pdf).
  • Lecture 14 (10/31): Primality Testing – 1. Notes (pdf).
  • Lecture 15 (11/02): Primality Testing – 2. Notes (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 (pdf).
  • Lecture 18 (11/14): Groebner bases (contd.). Notes (pdf).
  • Lecture 19 (11/16): Complexity of Ideal Membership. Notes (pdf).
  • Lecture 20 (11/21): Hilbert’s Nullstellensatz. Notes (pdf).
  • Lecture 21 (11/23): Quantifier Elimination. Notes (pdf).
  • (11/24-11/25): Thanksgiving.
  • Lecture 22 (11/28):  Algebraic computation models. Some lower bound techniques. Notes (pdf).
  • Lecture 23 (11/30):  Lower bound for multi-point polynomial evaluation; Bezout’s Theorem. Notes (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.