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/ST15/

Ever wondered why we can find the greatest common divisors of two integers, without knowing how to factor either? Why are polynomials easy to factor when integer factorization seems hard? Algorithms associated with algebraic operations are often extremely surprising. They are also quite ingenious – who would have thought that the identity “x^q – x = prod_{a in F_q} (x-a)” can be an algorithmic tool? Why is randomness such a powerful tool in algebraic algorithms often giving exponential speedups on best known deterministic algorithms? And what do algebraic algorithms have to do with the Rubik’s cube? In this course we will explore some of these questions and use them as a motivation to study algebra and computing a bit more systematically.

  • The first part will cover some strikingly efficient algorithms in Algebra, Number Theory, and Group Theory. Some topics include algorithms for membership testing in groups, factoring polynomials (Berlekamp,  Lenstra-Lenstra-Lovasz, Kaltofen etc.), algorithms for testing primes (Agarwal-Kayal-Saxena), solving systems of polynomial equations, ideal membership.
  • 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. Introduction to the Valiant and Blum-Shub-Smale models of arithmetic complexity.Role of the permanent and determinant. Depth-reduction in arithmetic complexity. Connection between deterministic polynomial identity testing and lower bounds for the permanent.

See http://people.csail.mit.edu/madhu/FT98,  http://people.csail.mit.edu/madhu/FT05 and http://people.csail.mit.edu/madhu/ST12 for details of earlier versions of this course.

Instructor: Madhu Sudan

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

Grading Policy

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 (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