In 1975, Goppa suggested to construct and analyze codes using machinery from algebraic function fields, and in a long line of research, such codes were eventually constructed. This field of mathematics is far deeper than the standard tools generally used by theoretical computer scientists, and the hope is that it can be further exploited in resolving other open problems. For that to happen, the theory should be grasped by computer scientists. This is the goal of this course.

In this course we will build the required theory of algebraic function fields, assuming minimal mathematical background, up to the point of constructing algebraic geometry codes. We then continue further and study other applications of the theory to computer science and, if time permits, also to cryptography.

The photograph was taken by Irit Dinur

- Two motivating examples - error correcting codes and small-bias sets (one lecture)
- Abstract algebra review (one and a half lectures)
- The geometric perspective - algebraic curves (two and a half lectures)
- An algebraic treatment - basics of algebraic function fields (three and a half lectures)
- (Finally!) Goppa codes (half a lecture)
- Extensions of function fields (one lecture)
- The Hermitian function field and BenAroya-TaShma's construction of small bias sets (one lecture)
- Hitting set generators for low-degree polynomials (one lecture)
- Kummer's theorem, Hurwitz genus formula, and optimal function fields over F_4 (one lecture)
- Optimal function fields and AG codes via Deuring polynomials (one lecture)

- Assignment 1
- Assignment 2
- Assignment 3
- Assignment 4
- Assignment 5
- Assignment 6
- Assignment 7
- Assignment 8
- Assignment 9
- Assignment 10

If you need to refresh your abstract algebra, I recommend Herstein's abstract algebra, which is a fun read. A great video course by Benedict Gross from Harvard is available online on YouTube.

If you, like me, enjoy watching video lectures on top of the reading material, then there is a great mini-course by Beelen that assumes some background, though it should be accessible towards the middle of the semester, and also covers topics we do not, such as decoding of AG codes. Highly recommended! (there is a small bug in the links there - lecture 2 and 4 were switched). Also, for learning some more about small-bias sets, you can check out Amir Yehudayoff's video lecture.

Location: Feinberg, room 4.

Back to my homepage.