Algebra and Computation (MIT
Prereq: 6.840 + 6.046 +
Time: MW 11:00-12:30pm
3-0-9 H-Level Grad Credit
This course studies
the interplay between algebra and computation. The course will be
divided in two parts.
for notes from an earlier version of this course.
- 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
- 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.
Alert: Please email the instructor asap
if you are interested in the course.