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.