6.885 Course announcement

Prereq: 6.840 + 6.046 + 18.703
Time: MW 11:00-12:30pm
Location: 36-155
3-0-9 H-Level Grad Credit
Homepage: http://theory.csail.mit.edu/~madhu/FT05/

Algebra and Computation

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

The first part will cover 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 (Cohn-Umans), 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://theory.csail.mit.edu/~madhu/FT98 for notes from an earlier version of this course.

Instructor: Madhu Sudan