{
  "annotation_id": "2299224b-3ef4-4217-bc15-18acbf4765d0",
  "date_created": "2026-02-17T05:53:11.268000Z",
  "date_modified": "2026-02-17T05:53:11.268000Z",
  "file_hash": "4a5333b7782c0b1ecefe8693793e6d56bd26275bb18a0bf9b797a05061019402",
  "private": false,
  "record": {
    "abstract": "Let $g(X)$ be a polynomial over a finite field ${\\mathbb F}_q$ with degree $o(q^{1/2})$, and let $\\chi$ be the quadratic residue character. We give a polynomial time algorithm to recover $g(X)$ (up to perfect square factors) given the values of $\\chi \\circ g$ on ${\\mathbb F}_q$, with up to a constant fraction of the values having errors. This was previously unknown even for the case of no errors.\n  We give a similar algorithm for additive characters of polynomials over fields of characteristic $2$. This gives the first polynomial time algorithm for decoding dual-BCH codes of polynomial dimension from a constant fraction of errors.\n  Our algorithms use ideas from Stepanov\u0027s polynomial method proof of the classical Weil bounds on character sums, as well as from the Berlekamp-Welch decoding algorithm for Reed-Solomon codes. A crucial role is played by what we call *pseudopolynomials*: high degree polynomials, all of whose derivatives behave like low degree polynomials on ${\\mathbb F}_q$.\n  Both these results can be viewed as algorithmic versions of the Weil bounds for this setting.",
    "arxiv_id": "2601.07137",
    "authors": [
      "Swastik Kopparty"
    ],
    "categories": [
      "cs.CC",
      "cs.IT",
      "math.IT",
      "math.NT"
    ],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "title": "Recovering polynomials over finite fields from noisy character values",
    "url": "https://arxiv.org/abs/2601.07137",
    "version": "v1"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "3e0ddd08-b494-4605-b40a-5cce47ad956b",
    "id": "arXiv Dataset",
    "type": "Model",
    "variant": "snapshot-2026-01-17",
    "version": "0.1.0"
  },
  "user_id": 1000002
}