Subquadratic Time Encodable Codes Beating the Gilbert–Varshamov Bound
Anand Kumar Narayanan, Matthew Weidner · IEEE Transactions on Information Theory · 2019
We construct explicit algebraic geometry codes built from the Garcia-Stichtenoth function-field tower beating the Gilbert-Varshamov bound for alphabet sizes at least 192. Messages are identified with functions in certain Riemann- Roch spaces associated with divisors supported on multiple places. Encoding amounts to evaluating these functions at degreeone places. By exploiting algebraic structures particular to the Garcia-Stichtenoth tower, we devise an intricate deterministic ω/2 <; 1.19 runtime exponent encoding and 1 + ω/2 <; 2.19 expected runtime exponent randomized (unique and list) decoding algorithms. Here ω <; 2.373 is the matrix multiplication exponent. If ω = 2, as widely believed, the encoding and decoding runtimes are respectively nearly linear and nearly quadratic. Prior to this work, encoding time of code families beating the Gilbert-Varshamov bound were quadratic or worse.