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.