Introduction to Algberaic-Geometric Codes

Spring 2019

Course Pitch (a.k.a. Syllabus)

Theoretical computer scientists make a regular use of algebraic objects, most prominently polynomials over finite fields, to construct and analyze desired objects such as error correcting codes, expander graphs, pseudorandom generators, cryptographic protocols, and randomness extractors. Reed-Solomon codes is one such classic example. In 1975, Goppa suggested to construct and analyze codes using machinery from algebraic geometry or, more precisely, based on algebraic curves. In a long line of research, such codes were eventually constructed. Surprisingly, these codes beat the Gilbert-Varshamov bound for sufficiently large (constant size) fields.

The mathematics underlying Goppa codes 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, especially problems for which using polynomials one currently obtains the state-of-the-art results. Indeed, many important problems fall into this category. For that to happen, the underlying mathematics must be grasped by computer scientists. This is the goal of this course (and its follow-up).

In this introductory course we will thoroughly develop the fascinating mathematics underlying algebraic curves to the point where Goppa's framework can be defined and well-understood - a modest yet challenging goal. The approach we take is mostly algebraic, however, we will not abandon the geometric aspect - we will "think geometrically" and prove theorems algebraically. Students who complete the course should be able to use the mathematical tools developed beyond the code-specific application.

Who this course is for?

The target audience for the course is computer science graduate and advanced undergraduate students that would like to study fascinating, deep mathematics and employ it in their own research. I will assume basic knowledge in ring theory and field theory. This was covered in a course I gave last semester as in any standard course on abstract algebra. I will not assume knowledge in topology, commutative algebra or Galois theory - we'll develop all we need.

Slides

So, initially, I was hoping to deliver this course on board like any good old math course. However, this turned out to be difficult in terms of time. So, we are switching to slides now:

Lecture 6 (April 29, 2019)

In this lecture, we studied the following three units + the construction of the field of fractions with respect to a multiplicative set that appears in the next unit.

Lecture 7 (May 6, 2019)

We study the important commutative algebraic tool of localization and use it to prove an important result regarding algebraic curves.

Lecture 8 (May 13, 2019)

Lecture 9 (May 20, 2019)

Lecture 10 (May 27 2019)

Lecture 11 (June 3 2019)

• Projective curves

Lecture 12 (June 10 2019)

You can access the old notes here.

Assignments and Final

When and where

Lectures: Monday 12:10-15:00, Orenstein 111

Recitations: Wednesday 10:10-11:00, Orenstein 103

About 8-10 light assignments will be given during the semester. These will account for 50% of the grade. The remaining 50% will be determined by a take-home exam.