Algebra and Computation (MIT 6.S897)

General Info:
  • Lecturer: Madhu Sudan;  32-G640; email: first name at mit dot edu
  • TA: None. Voluntary help welcome.
  • Units: 3-0-9 H Level Grad Credit;
  • Time and Location: MW 11-12:30 in 34-304
Announcements:

Tentative schedule of topics:

  • Lecture 01 (Wed. 02/08): CANCELLED.
  • Lecture 02 (Mon. 02/13): Administrivia, Course Contents. Membership in permutation groups. Notes ((updated 2/21/2012) tex, pdf).
  • Lecture 03 (Wed. 02/15): Review of algebra: Existence and Uniqueness of Fields. Notes ((updated 3/10/2012) tex, pdf).
  • Monday (02/20):  President's Day holiday.
  • Lecture 04 (Tue. 02/21): Computation with polynomials - basic problems. Fast polynomial multiplication. Prenotes (pdf). Notes (tex, pdf).
  • Lecture 05 (Wed. 02/22): CANCELLED.
  • Lecture 06 (Mon. 02/27): Fast polynomial division, GCD. Prenotes (pdf). Notes ((updated 3/8/2012) tex, pdf).
  • Lecture 07 (Wed. 02/29): Polynomial factorization: Randomized over all fields; deterministic over fields of small characteristic. Prenotes (pdf). Notes (tex, pdf).
  • Lecture 08 (Mon. 03/05): Factorization of multivariate polynomials. Bezout's theorem. Prenotes (pdf). Notes (tex, pdf)
  • Lecture 09 (Wed. 03/07): Guest Lecturer: Eli Ben-Sasson. The Lenstra-Lenstra-Lovasz (LLL) algorithm. Prenotes (pdf). Notes (tex, pdf).
  • Lecture 10 (Mon. 03/12): Hensel Lifting. (Incomplete) Prenotes (pdf). Notes (tex, pdf).
  • Lecture 11 (Wed. 03/14): Factorization of multivariate polynomials - conclusion. Prenotes (pdf). Notes ((updated 4/12/2012) tex, pdf).
  • Lecture 12 (Mon. 03/19): Primality testing. Prenotes (pdf). Notes (tex, pdf).
  • Lecture 13 (Wed. 03/21): Guest Lecturer: Eli Ben-Sasson. Extracting randomness from algebraic sources. Notes (tex, pdf).
  • (03/26-03/30): Spring Break
  • Lecture 14 (Mon. 04/02): Systems of polynomial equations: Some problems. Notes (tex, pdf).
  • Lecture 15 (Wed. 04/04): Ideal membership problem. Gröbner basis. Prenotes (pdf). Notes (tex, pdf).
  • Lecture 16 (Mon. 04/09): Complexity of Ideal Membership. Prenotes (pdf). Notes (tex, pdf).
  • Lecture 17 (Wed. 04/11): Hilbert Nullstellensatz. Quantifier elimination.  Prenotes (pdf). Notes (tex, pdf).
  • (Mon. 04/16 + Tue. 04/17): Patriots Day holiday.
  • Lecture 18 (Wed. 04/18): Arithmetic Complexity: Models, Problems, Classes, Basic Stuff. Prenotes (pdf). Notes (tex, pdf).
  • Lecture 19 (Mon 04/23): Polysize circuit for determinant. Depth Reduction. Partial Derivatives. Prenotes (pdf). Notes (tex, pdf).
  • Lecture 20 (Wed. 04/25): Lower bounds for multi-point polynomial evaluation. Strassen's proof. Smolensky's proof. Prenotes (pdf). Notes (tex, pdf).
  • Lecture 21 (Mon. 04/30): Applications of Algebra in Computing: Codes and Decoding. Prenotes (pdf). Notes (tex, pdf)
  • Lecture 22 (Wed. 05/02): Applications of Algebra in Computing: Probababilistically Checkable Proofs. Prenotes (pdf). Notes (tex, pdf).
  • Lecture 23 (Mon. 05/07):  Applications of Algebra in Computing: Locally Decodable Codes. Prenotes (pdf). Notes (tex, pdf).
  • Project Presentations: Day 1 (Time TBD).
  • Lecture 24 (Wed. 05/09):  Locally decodable codes of [Yekhanin, Raghavendra, Efremenko]. Prenotes (pdf). Notes (tex, pdf).
  • Project Presentations: Day 2 (Time TBD).
  • Lecture 25 (Mon. 05/14):  CANCELLED.
  • Lecture 26 (Wed. 05/16):  CANCELLED.

References:

uuuuuuu