Constant query codes correct errors over real number grids

Constant query LCCs over the reals

Computational Complexity

Summary

Some codes let you fix mistakes quickly by checking only a few parts, but before, this was mostly possible over specific mathematical fields, not the real numbers. The authors found a way to create such codes over real numbers using curves that pass through points on a grid, which helps find errors by looking nearby. This challenges earlier beliefs that such quick correction codes couldn't exist over the real numbers. The method also makes sure that no part of the grid is checked too often, spreading out the work evenly.

What this means in practice

  • For data storage engineers: Create error-correcting schemes for data stored with real-valued measurements that allow correcting errors by checking only a few related data points nearby.
  • For signal processing developers: Design robust recovery algorithms for signals represented over grids of real numbers using low-degree polynomials and local queries along curves.

Authors

Zeev Dvir

Abstract

This note describes a new construction, found by ChatGPT Astra, of constant query Locally Correctable Codes (LCCs) over the real numbers. Prior constructions of constant query LCCs were exclusive to fields of positive characteristic and were conjectured not to exist over the reals. The construction uses low degree polynomial evaluations over an integer grid, together with a novel sampling procedure which outputs, for a given grid point $P$, a random quadratic curve through $P$ which intersects the grid in many other points (the decoding queries). The sampler is `smooth' in the sense that no grid point is queried with high probability. These codes have the additional property that the queried locations (the curve/grid intersections) are all nearby grid points.