Subquadratic Time Encodable Codes Beating the Gilbert-Varshamov Bound
- Creators
- Narayanan, Anand Kumar
- Weidner, Matthew
Abstract
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.
Additional Information
© 2019 IEEE. Manuscript received August 11, 2018; accepted June 23, 2019. Date of publication July 23, 2019; date of current version September 13, 2019. This work was supported in part by the NSF under Grant CCF-1423544, in part by Chris Umans' Simons Foundation Investigator Grant, in part by the European Union's H2020 Programme under Grant ERC-669891, and in part by Caltech's Rita A. and Øistein Skjellum SURF Fellowship. We would like to thank the reviewers for their suggestions.Additional details
- Eprint ID
- 97429
- DOI
- 10.1109/tit.2019.2930538
- Resolver ID
- CaltechAUTHORS:20190726-073353508
- CCF-1423544
- NSF
- Simons Foundation
- 669891
- European Research Council (ERC)
- Caltech Summer Undergraduate Research Fellowship (SURF)
- Created
-
2019-07-26Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field