6.S897 Algebra and Computation


Graduate H-Level
Units: 3-0-9
Prerequisites: 6.840J and 6.046J and 18.073
Instructor:  Prof. Madhu Sudan
Schedule: MW11-12:30, room room 34-304

  • 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.