skip to main content

Theory Group Meeting

Tuesday, April 17, 2018
4:00pm to 5:00pm
Add to Cal
Annenberg 322
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].