## Algebraic Geometry for Theoretical Computer Science

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.

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