Algebraic Geometry for Theoretical Computer Science

What this course is about?

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.

Syllabus

Taken by Irit Dinur

  • Two motivating examples - error correcting codes and small-bias sets

  • Abstract algebra review

  • The geometric perspective - algebraic curves

  • An algebraic treatment - basics of algebraic function fields

  • (Finally!) Goppa codes

  • Extensions of function fields

  • The Hermitian function field and BenAroya-TaShma's construction of small bias sets

  • Hitting set generators for low-degree polynomials

  • Kummer's theorem, Hurwitz genus formula, and optimal function fields over GF(4)

  • Optimal function fields and AG codes via Deuring polynomials

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. 

Assignments

Literature and useful links

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.