Course announcement

Algebra and Computation (MIT 6.S897)

Prereq: 6.840 + 6.046 + 18.703
Time: MW 11:00-12:30pm
Location: 34-304
3-0-9 H-Level Grad Credit
Homepage: http://people.csail.mit.edu/madhu/ST15/

Ever wondered why we can find the greatest common divisors of two integers, without knowing how to factor either? Why are polynomials easy to factor when integer factorization seems hard? Algorithms associated with algebraic operations are often extremely surprising. They are also quite ingenious - who would have thought that the identity "x^q - x = prod_{a in F_q} (x-a)" can be an algorithmic tool? Why is randomness such a powerful tool in algebraic algorithms often giving exponential speedups on best known deterministic algorithms? And what do algebraic algorithms have to do with the Rubik's cube? In this course we will explore some of these questions and use them as a motivation to study algebra and computing a bit more systematically.

The first part will cover some strikingly efficient algorithms in Algebra, Number Theory, and Group Theory. Some topics include algorithms for membership testing in groups, factoring polynomials (Berlekamp, Lenstra-Lenstra-Lovasz, Kaltofen etc.), algorithms for testing primes (Agarwal-Kayal-Saxena), solving systems of polynomial equations, ideal membership.
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. Introduction to the Valiant and Blum-Shub-Smale models of arithmetic complexity.Role of the permanent and determinant. Depth-reduction in arithmetic complexity. Connection between deterministic polynomial identity testing and lower bounds for the permanent.

See http://people.csail.mit.edu/madhu/FT98, http://people.csail.mit.edu/madhu/FT05 and http://people.csail.mit.edu/madhu/ST12 for details of earlier versions of this course.

Instructor: Madhu Sudan

Alert: Please email Madhu asap if you are interested in the course.