Theory Group Meeting
Subquadratic time encodable codes beating the Gilbert-Varshamov bound
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 email@example.com