error-correcting code engineers

Abstract: Local coordinate-wise linear (LCL) properties provide a unified framework for studying list decoding, list recovery and other local properties of linear codes. We prove that random one-point algebraic geometry (AG) codes have the same LCL threshold rates as random linear codes under explicit alphabet and sampling conditions. More precisely, for a family of local profiles with random linear code threshold $R_{\mathcal P}$, a random one-point AG code avoids all such profiles below $R_{\mathcal P}-\varepsilon$ and contains one above $R_{\mathcal P}+\varepsilon$, with explicit failure bounds on both sides. Our proof also removes an auxiliary lower bound on the number of available rational places that arises in a direct adaptation of the Reed--Solomon argument and requires no additional genus-dependent rate gap. We also observe that the previously claimed above threshold proof for random Reed--Solomon codes does not establish the required probability lower bound. The containment relation used in that argument gives the probability comparison in the opposite direction from what is needed. We give a different above threshold argument, which in particular also yields an alternative proof in the genus zero case. Combining our threshold theorem with recent results for random linear codes gives a collection of new list decoding, average weight list decoding and list recovery guarantees for random one-point AG codes. We further obtain new correlated agreement and proximity gap results for polynomial curves. These results extend the LCL threshold framework from random linear and Reed--Solomon codes to random one-point AG codes.

Abstract: When computing with univariate polynomials, two fundamental and related problems are the XGCD and rational reconstruction, classically solved in quasi-linear complexity using the half-gcd algorithm. These problems have various applications in algebraic computations and bear strong connections to linearly recurrent sequences, structured matrices, and continued fractions. This article first gives a collection of algorithmic reductions, showing that rational reconstruction and XGCD can be solved via the computation of bases of relations modulo a freely-chosen polynomial $M(x)$. In particular, one recovers the folklore idea that bases of Padé approximants (i.e., $M(x) = x^d$) can be used to perform quasi-linear rational reconstruction or XGCD, extending to fast algorithms the well-known link between the Berlekamp-Massey algorithm and the extended Euclidean algorithm. One highlight of these reductions is that, instead of approximants, one may rely on Cauchy interpolants (i.e., $M(x)$ vanishes at chosen points). In a second part, this article describes divide-and-conquer algorithms for approximants and interpolants along with complexity analyses showing an explicit leading constant in front of the dominant term. For interpolants, the best leading constant is obtained through a variant that stores polynomials represented by evaluations, and exploits fast extrapolation in order to avoid repeated conversions to the monomial basis; this requires special points, in geometric or arithmetic progression, or FFT points when the base field allows them. Combining the analyses with the reductions leads to the best complexity bounds we are aware of for rational reconstruction and XGCD. Perhaps surprisingly, even Padé approximants or Berlekamp-Massey-like computations, which intrinsically involve $M(x) = x^d$, are accelerated by reducing them to Cauchy interpolation at well-chosen points.