Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Correlated algebraic-geometric codes: Improved list decoding over bounded alphabets
HTML articles powered by AMS MathViewer

by Venkatesan Guruswami and Anindya C. Patthak PDF
Math. Comp. 77 (2008), 447-473

Abstract:

We define a new family of error-correcting codes based on algebraic curves over finite fields, and develop efficient list decoding algorithms for them. Our codes extend the class of algebraic-geometric (AG) codes via a (nonobvious) generalization of the approach in the recent breakthrough work of Parvaresh and Vardy (2005). Our work shows that the PV framework applies to fairly general settings by elucidating the key algebraic concepts underlying it. Also, more importantly, AG codes of arbitrary block length exist over fixed alphabets $\Sigma$, thus enabling us to establish new trade-offs between the list decoding radius and rate over a bounded alphabet size. The work of Parvaresh and Vardy (2005) was extended in Guruswami and Rudra (2006) to give explicit codes that achieve the list decoding capacity (optimal trade-off between rate and fraction of errors corrected) over large alphabets. A similar extension of this work along the lines of Guruswami and Rudra could have substantial impact. Indeed, it could give better trade-offs than currently known over a fixed alphabet (say, $\textrm {GF}(2^{12})$), which in turn, upon concatenation with a fixed, well-understood binary code, could take us closer to the list decoding capacity for binary codes. This may also be a promising way to address the significant complexity drawback of the result of Guruswami and Rudra, and to enable approaching capacity with bounded list size independent of the block length (the list size and decoding complexity in their work are both $n^{\Omega (1/\varepsilon )}$ where $\varepsilon$ is the distance to capacity). Similar to algorithms for AG codes from Guruswami and Sudan (1999) and (2001), our encoding/decoding algorithms run in polynomial time assuming a natural polynomial-size representation of the code. For codes based on a specific “optimal” algebraic curve, we also present an expected polynomial time algorithm to construct the requisite representation. This in turn fills an important void in the literature by presenting an efficient construction of the representation often assumed in the list decoding algorithms for AG codes.
References
Similar Articles
Additional Information
  • Venkatesan Guruswami
  • Affiliation: Department of Computer Science & Engineering, University of Washington, Seattle, Washington 98195
  • Email: venkat@cs.washington.edu
  • Anindya C. Patthak
  • Affiliation: Department of Computer Science, University of Texas at Austin, Austin, Texas 78712
  • Email: anindya@cs.utexas.edu
  • Received by editor(s): July 26, 2006
  • Received by editor(s) in revised form: November 14, 2006
  • Published electronically: September 13, 2007
  • Additional Notes: An extended abstract describing some of these results was presented at the 47th Annual Symposium on Foundations of Computer Science (FOCS), 2006. This is an expanded version of the paper, containing the proofs and algorithms in full
    The first author was supported by NSF Career Award CCF-0343672, an Alfred P. Sloan Research Fellowship, and a David and Lucile Packard Foundation Fellowship
    The second author was supported in part by NSF Grant CCR-0310960
  • © Copyright 2007 Venkatesan Guruswami and Anindya C. Patthak
  • Journal: Math. Comp. 77 (2008), 447-473
  • MSC (2000): Primary 94B27, 12Y05, 14Q05, 14H05
  • DOI: https://doi.org/10.1090/S0025-5718-07-02012-1
  • MathSciNet review: 2353961