Theory Group Meeting

ABSTRACT:  Random linear codes have good parameters as the code length goes to infinity, meeting the so-called Gilbert-Varshamov bound.
However, they have encoding time quadratic in the code length.
Algebraic geometry codes have been known since 1980s to also give long codes beating the Gilbert-Varshamov bound, but the fastest known encoding algorithm for optimal codes takes cubic time to write down a generator matrix.  Recently, Anand Kumar Narayanan and I have constructed specific subcodes of algebraic geometry codes which beat the Gilbert-Varshamov bound and can be encoded with runtime exponent 3/2. I will give a quick introduction to algebraic geometry codes before describing our construction and encoding algorithm.