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 (topics of lectures are still TBD):

  • Lecture 01 (Wed. 02/04): Administrivia, Course Contents. Membership in permutation groups. Prenotes (pdf). Notes (tex, pdf).
  • Lecture 02 (Mon. 02/09): Madhu out of town - Lecture contents and Lecturer TBD
  • Lecture 03 (Wed. 02/11): Madhu out of town - Lecture contents and Lecturer TBD
  • Monday (02/16):  President's Day holiday.
  • Lecture 04 (Tue. 02/17): Review of algebra: Existence and Uniqueness of Fields. Notes (tex, pdf).
  • Lecture 05 (Wed. 02/18): Computation with polynomials - basic problems. Fast polynomial multiplication. Prenotes from Spring 2012 (pdf). Notes (tex, pdf).
  • Lecture 06 (Mon. 02/23): Fast polynomial division, GCD; Factorization - 1. Prenotes from Spring 2012 (here, here, and here). Notes (tex, pdf).
  • Lecture 07 (Wed. 02/25): Polynomial factorization: Randomized over all fields; deterministic over fields of small characteristic. Minimal polynomials. Prenotes from Spring 2012 (pdf). Notes (tex, pdf).
  • Lecture 08 (Mon. 03/02): Factorization of multivariate polynomials. Resultant. Bezout's theorem. Prenotes from Spring 2012 (pdf). Notes (tex, pdf).
  • Lecture 09 (Wed. 03/04): Factorization of bivariate polynomials (contd.). Notes + Addendum (tex, pdf).
  • Lecture 10 (Mon. 03/09): Fatorization of univariate polynomials over the rationals. Notes (tex, pdf).
  • Lecture 11 (Wed. 03/11): The LLL algorithm for finding short vectors in lattices. Prenotes from Spring 2012 (pdf). Notes (tex, pdf).
  • Lecture 12 (Mon. 03/16): Primality testing-1. Prenotes from Spring 2012 (pdf). Notes (tex, pdf).
  • Lecture 13 (Wed. 03/18): Primality testing-2. Notes (tex, pdf).
  • (03/23-03/28): Spring Break
  • Lecture 14 (Mon. 03/30): Arithmetic Complexity: Models, Problems, Classes, Basic Stuff. Prenotes from Spring 2012 (pdf). Notes (tex, pdf).
  • Lecture 15 (Wed. 04/01): Polysize circuit for determinant. Depth Reduction. Partial Derivatives. Prenotes from Spring 2012 (pdf). Notes (tex, pdf).
  • Lecture 16 (Mon. 04/06): Depth Reduction (contd.). Notes (tex, pdf).
  • Lecture 17 (Wed. 04/08): Lower bounds for multi-point polynomial evaluation. Strassen's proof. Smolensky's proof.  Prenotes from Spring 2012 (pdf). Notes (tex, pdf).
  • Lecture 18 (Mon. 04/13): Smolensky's proof contd. Determinant, Permanent. Depth 4 circuits and lower bounds. Notes (tex, pdf).
  • Lecture 19 (Wed. 04/15): Conclude arithmetic circuits. Complexity of Ideal membership, Nullstellensatz etc. Notes (tex, pdf).
  • (Mon. 04/20 + Tue. 04/21): Patriots Day holiday.
  • Lecture 20 (Wed. 04/22): Ideal membership and Groebner bases. Prenotes from Spring 2012 (pdf). Notes (tex, pdf). 
  • (Thu. 04/23): DROP DATE.
  • Lecture 21 (Mon. 04/27): Complexity of Ideal Membership. Hilbert Nullstellensatz. Quantifier Elimination. Prenotes from Spring 2012 (pdf). Notes (tex, pdf).
  • Lecture 22 (Wed. 04/29): Applications of Algebra in Computing: Codes and Decoding. Notes (tex,pdf).
  • Lecture 23 (Mon. 05/04):  Applications of Algebra in Computing: Folded Reed-Solomon Codes. Locally Decodable Codes. Prenotes (pdf). Notes (tex, pdf).
  • Lecture 24 (Wed. 05/06):  Locally decodable codes of [Yekhanin, Raghavendra, Efremenko]. Prenotes (pdf). Notes (tex, pdf).
  • Lecture 25 (Mon. 05/11):  Project presentations.
  • Lecture 26 (Wed. 05/13):  Project presentations.

References:

uuuuuuu