List Decoding of Algebraic Geometric Codes

PhD of University Paris VI
(now UPMC Sorbonne University)

Research carried out, between 1997 and 2001, at Project CODES (now SECRET) at l’INRIA, under the supervision of Pascale Charpin, Research Director at INRIA, Project CODES Director, and of Daniel Augot, Researcher at INRIA.

For a general public introduction to coding theory, you may read my article L’algèbre qui corrige les erreurs (in French). A description of my work for scientists who are not specialists of coding theory is available here

Abstract: Algebraic-geometric codes were introduced by Goppa in 1981 and are built using algebraic curves over finite fields. In 1982, Tsfasman, Vladuts and Zink showed that one could build a family of such codes that beats the Gilbert-Varshamov bound. In 1996, Sudan proposed a list decoding algorithm for Reed-Solomon codes. This algorithm was adapted in 1997 to one-point strongly algebraic-geometric codes by Shokrollahi and Wasserman, then improved by Guruswami and Sudan.

In this thesis, we extend these methods to all algebraic-geometric codes and their subfield subcodes, and to a generalized Hamming distance that allows to reformulate algebraically the soft decision decoding problem and to propose a maximum likelihood list decoding algorithm over any discrete memoryless channel. We illustrate these new results with an implementation in the computer algebra system Magma.

NB: there are still a few errors I never had the courage to correct.

2000 Mathematics Subject Classification: 11T71 Algebraic coding theory; cryptography; 94B35 Decoding; 94B27 Geometric methods (including applications of algebraic geometry) [See also 11T71, 14G50]; 11Yxx Computational number theory [See also 11-04]; 14Qxx Computational aspects in algebraic geometry [See also 12Y05, 13Pxx, 68W30]; 68W30 Symbolic computation and algebraic computation [See also 11Yxx, 12Y05, 13Pxx, 14Qxx, 16Z05, 17-08, 33F10].

Keywords: List decoding; maximum-likelihood soft-decision decoding; algebraic-geometric codes; Reed-Solomon codes; subfield subcodes; Guruswami-Sudan’s algorithm; effective algebraic geometry; algorithmic number theory; roots of polynomials on function fields of curves over a finite field; computer algebra; Magma implementation.

Defense: This thesis as awarded summa cum laude after a defense that took place on Tuesday Decembrer 18th, 2001 at 14:00, Jussieu Campus, 4, place Jussieu, 75005 Paris, France. The jury was consisting of:

  • Daniel Lazard: Professor (Paris VI), President of the Jury
  • Pascale Charpin: Research Director (INRIA), PhD Advisor
  • Daniel Augot: Researcher (INRIA), PhD Co-advisor
  • Claude Carlet: Professor (Caen), Referee
  • Tom Høholdt: Professor (DTU, Denmark), Referee
  • François Morain: Professeur (Polytechnique), Examiner

“Non technical” description for scientists who are not specialists in coding theory


Coding Theory’s main goal is to improve mathematically the reliability of telecommunications. Its foundations were built in the middle of the 20th century with the work of Claude Shannon, Richard Hamming, and others.

The introduction of algebraic-geometric tools by Goppa allowed him to build in 1981 some codes, naturally called “algebraic-geometric”, from curves over finite fields. These codes beneficiate from the powerful Riemann-Roch Theory that allows, in particular, to estimate the fundamental parameters of such codes that are their minimum distance and their dimension.

In 1982, Michael Tsfasman, Serge Vladuts and Thomas Zink could exhibit a family of explicit algebraic-geometric codes that were better than all known codes at that time and whose performance was beating the Gilbert-Varshamov bound that was (wrongly) conjectured to be optimal.

In 1996, Madhu Sudan proposed a method for the list decoding of Reed-Solomon codes, that was adapted in 1997 by Amin Shokrollahi and Hal Wasserman to one-point strongly algebraic-geometric codes, and improved again by Venkatesan Guruswami and Sudan.

Contributions of this thesis

  1. The generalization of Guruswami-Sudan’s algorithm to all algebraic-geometric codes
  2. The description of a list decoding algorithm for a distance that generalizes the Hamming distance and that allows an algebraic soft decision decoding that maximizes the likelihood on any discrete memoryless channel
  3. Some refinements of existence conditions for auxilliary polynomials that are used in list decoding algorithms
  4. An evaluation that takes into account the data structures and algorithmic primitives that are required to use the geometric structure of codes (curve, normalized curve, genus, divisors, Riemann-Roch spaces) for their list decoding
  5. An implementation in Magma of a desingularization algorithm of a plane model of a curve and of an improved version of the Brill-Noether algorithm. This allows in particular, the computation of p-adic series of fonctions in any closed point p of the curve and its genus (joint work with Pawel Wocjan)
  6. The implementation in Magma of a communication channels library that allows to test our soft decision algorithm
  7. The adaptation of Newton-Puiseux’s algorithm for finding roots of polynomials over function fields, that provides one of the primitives used in the list decoding algorithm
  8. The proof of a combinatoric property of low-rate codes that allows to use, in that case, Newton-Hensel’s algorithm, which dramatically reduces the complexity of their list decoding to essentially quadratic time (joint work with Daniel Augot)
  9. The proof that one can precompute sufficient information for not having to use effective Riemann-Roch Theory during list decoding
  10. A complete implementation in Magma of the above methods, in particular of our generalized list decoding algorithm and its soft decision version

Curves for Coding and Cryptography

In this elementary and introductory talk at INRIA‘s Junior Colloquium, we present the usual problems that occur in the theory of error-correcting codes and of cryptography. We show how the use of effective algebraic geometry over finite fields can help to solve some of the questions that arise in these disciplines.

Eurocitizen report on Security and Defense

In 2007, threats are not only in distant countries anymore, terrorism strikes the heart of Europe, crime is increasingly powerful, media’s role is fundamental, information technologies are now critical for both corporations and individuals, European security and defence emerges…

This project was aiming at helping citizen discuss together and with experts and make their own mind on issues regarding national security and defense in France and in Europe, as a complement to the official debate, in a setting of major national¹ and international² reforms. The first version of the document can be found here.

¹White Book on Defense and National Security wrote by the Mallet Commission, Bauer project on strategic research, creation of the Direction Centrale du Renseignement Intérieur (DCRI), as a merge of the Direction Centrale des Renseignement Généraux (DCRG) and the Direction de la Surveillance du Territoire (DST), Balladur Commission on the modernization of Vth Republic’s institutions, Révision Générale des Politiques Publiques (RGPP), justice reforms, etc.

² Lisbon’s Treatee signature and French Presidence of the Council of the European Union in 2008.

Functional Programming

Functional Programming handout, BSc in Computer Science

Functional Programming Course, BSc in Computer Science, University Paris XII (2001-2003)

Découvrez Objective Caml

Published in GNU/Linux & Hurd Magazine France n° 43 (Oct. 2002)

Objective Caml (aka Ocaml) is a wonderful programming language: flexible, safe, efficient, equipped with many libraries (graphics, network,…). It is often seen as a curiosity used only by theoretical computer scientists. In this article, we briefly browse the genealogical tree of this language to understand its main principles and to familiarize the reader with functional programming; then we present the different working modes and some of the original aspects of this language. We finish with a small example that features the graphics and Unix libraries and with the evocation of other developping tools that are available for Ocaml.

Resources about software validation and security

History’s Worst Software Bugs, by Simson Garfinkel, 2005.