Subquadratic Time Encodable Codes Beating the Gilbert–Varshamov Bound
| Autor: | Matthew Weidner, Anand Kumar Narayanan |
|---|---|
| Přispěvatelé: | Institut de Mathématiques de Jussieu - Paris Rive Gauche (IMJ-PRG), Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), ALgorithms for coMmunicAtion SecuriTY (ALMASTY), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS) |
| Rok vydání: | 2019 |
| Předmět: |
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
FOS: Computer and information sciences Computer Science - Information Theory [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] 02 engineering and technology Algebraic geometry Library and Information Sciences Computational Complexity (cs.CC) Omega 0202 electrical engineering electronic engineering information engineering FOS: Mathematics Number Theory (math.NT) Function field ComputingMilieux_MISCELLANEOUS Mathematics Computer Science::Information Theory Discrete mathematics [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] Mathematics - Number Theory Degree (graph theory) Information Theory (cs.IT) 020206 networking & telecommunications Matrix multiplication [MATH.MATH-NT]Mathematics [math]/Number Theory [math.NT] Computer Science Applications Gilbert–Varshamov bound Computer Science - Computational Complexity [INFO.INFO-IT]Computer Science [cs]/Information Theory [cs.IT] Exponent Decoding methods Information Systems |
| Zdroj: | IEEE Transactions on Information Theory IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2019, 65 (10), pp.6010-6021. ⟨10.1109/TIT.2019.2930538⟩ |
| ISSN: | 0018-9448 |
| DOI: | 10.1109/tit.2019.2930538 |
| Popis: | 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 identied with functions in certain Riemann-Roch spaces associated with divisors supported on multiple places. Encoding amounts to evaluating these functions at degree one places. By exploiting algebraic structures particular to the Garcia-Stichtenoth tower, we devise an intricate deterministic \omega/2 < 1.19 runtime exponent encoding and 1+\omega/2 < 2.19 expected runtime exponent randomized (unique and list) decoding algorithms. Here \omega < 2.373 is the matrix multiplication exponent. If \omega = 2, as widely believed, the encoding and decoding runtimes are respectively nearly linear and nearly quadratic. Prior to this work, encoding (resp. decoding) time of code families beating the Gilbert-Varshamov bound were quadratic (resp. cubic) or worse. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|