Harvard University homepage
HARVARD.EDU

Madhu Sudan: Algebra and Computation

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:

Course announcement

Algebra and Computation (MIT 6.S897)

Prereq: 6.840 + 6.046 + 18.703
Time: MW 11:00-12:30pm
Location: 34-304
3-0-9 H-Level Grad Credit
Homepage: http://people.csail.mit.edu/madhu/ST12/


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

  • The first part will cover some strikingly efficient 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 ((hopefully) Coppersmith-Winograd + Williams, Cohn-Umans-Kleinberg-Szegedy), 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 http://people.csail.mit.edu/madhu/FT98 and http://people.csail.mit.edu/madhu/FT05 for notes from an earlier version of this course.

Instructor: Madhu Sudan

Alert: Please email the instructor asap if you are interested in the course.

Grading Policy

Grading Policy for Algebra and Computation (MIT 6.S897):

Grades will be based on a combination of the following ingredients

  1. 2-4 Problem Sets.
  2. A course project (instructions to be posted shortly).
  3. Class Participation (biased towards the second half of the term).
  4. Additionally, you must scribe at least one lecture.

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: