Theory Group Meeting
Tuesday, April 17, 2018
4:00pm to 5:00pmAdd to Cal
Subquadratic time encodable codes beating the Gilbert-Varshamov bound
Matthew Weidner, Caltech,
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.
For more information, please contact Bonnie Leung by email at [email protected].