6.885 Algebra and Computation (H)

L MW11-12:30, room 36-155
Professor Madhu Sudan
Prereq.: 6.840J and 6.046J and 18.703
3-0-9

This subject qualifies as a theoretical computer science engineering concentration subject.

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), 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.