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

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.
See and for details of earlier versions of this course.

Instructor: Madhu Sudan

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