Algebraic Geometry for Theoretical Computer Science
Syllabus
Theoretical computer scientists regularly make use of algebraic structures such as finite fields and vector spaces to construct and analyze desired objects such as expander graphs, codes, pseudorandom generators and randomness extractors. It is safe to say that such algebraic structures are well grasped by the theoretical computer science community.
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
Summary of the course topics
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)
Background
The course is designed for computer science students (like me!). In particular, the only mathematical required background is a first course in linear algebra. Moreover, no background in coding theory is assumed.
Grading
The course is mathematical in nature and as such the theory must be practiced. Thus, each week a light assignment will be handed out, and will be graded as PASS or FAIL. Students interested in (two) credit points are required to submit all but two assignments with a passing grade. Another option, which you may choose instead of submitting assignments, is to present a paper at the end of the semester.
This course is not based on any specific book, as most sources are aimed for students with background in algebraic geometry (and no background in coding theory). There are great lecture notes of Morandi which assumes relatively sparse background. I recommend looking at them from time to time. In the part of the course devoted to function fields we will mainly follow the first chapter of Algebraic Function Fields and Codes. At the end of the semester, we will learn about towers of function fields. This part will be based on Chapter 7 of Algebraic Function Fields and Codes and on Chapter 1 of Topics in Geometry, Coding Theory and Cryptography. The lecture on small-bias sets will follow the original paper of Ben-Aroya and Ta-Shma.
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.
