Excellent codes from modular curves

DOI10.1145/380752.380802MaRDI QIDQ5175969zbMATH OpenOpenAlexFDO

Authors Noam D. Elkies

Publication date 27 February 2015

Published in Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0104115

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Applications to coding theory and cryptography of arithmetic geometry (14G50) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27)

Abstract: We introduce a new construction of error-correcting codes from algebraic curves over finite fields. Modular curves of genus g -> infty over a field of size q0^2 yield nonlinear codes more efficient than the linear Goppa codes obtained from the same curves. These new codes now have the highest asymptotic transmission rates known for certain ranges of alphabet size and error rate. Both the theory and possible practical use of these new record codes require the development of new tools. On the theoretical side, establishing the transmission rate depends on an error estimate for a theorem of Schanuel applied to the function field of an asymptotically optimal curve. On the computational side, actual use of the codes will hinge on the solution of new problems in the computational algebraic geometry of curves.

Recommendations

• Linear codes and modular curves
• Modular curves and coding theory: a survey
• Modular curves and codes with polynomial complexity of construction
• Modular curves and codes with a polynomial construction
• scientific article; zbMATH DE number 66120

Cites work

• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)

Cited in

(20)

• Elliptic codes over fields of characteristic 2
• Linear codes and modular curves
• An exhaustion bound for algebraic-geometric ``modular codes
• A special integral basis for a plane model of the Drinfeld modular curve \(X_1(n)\bmod T\)
• Nonuniform Fuchsian codes for noisy channels
• Further improvements on asymptotic bounds for codes using distinguished divisors
• Construction of codes from Arakelov geometry
• scientific article; zbMATH DE number 1594280 (Why is no real title available?)
• Spaces of modular forms and algebraic geometric codes
• Modular curves and coding theory: a survey
• Modular curves and codes with a polynomial construction
• Construction of global function fields from linear codes and vice versa
• scientific article; zbMATH DE number 3983069 (Why is no real title available?)
• scientific article; zbMATH DE number 4002031 (Why is no real title available?)
• scientific article; zbMATH DE number 1461541 (Why is no real title available?)
• scientific article; zbMATH DE number 1488180 (Why is no real title available?)
• Codes over rings from curves of higher genus
• Upper bounds for some Brill–Noether loci over a finite field
• Fuchsian codes with arbitrarily high code rates
• Nonlinear codes from points of bounded height

This page was built for publication: Excellent codes from modular curves

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5175969)