Theory Group Meeting

Tuesday April 17, 2018 4:00 PM

Subquadratic time encodable codes beating the Gilbert-Varshamov bound

Speaker: Matthew Weidner, Caltech
Location: Annenberg 322

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.

Contact: Bonnie Leung bjleung@caltech.edu