Recovering polynomials over finite fields from noisy character values
Let $g(X)$ be a polynomial over a finite field ${\mathbb F}_q$ with degree $o(q^{1/2})$, and let $χ$ be the quadratic residue character. We give a polynomial time algorithm to recover $g(X)$ (up to perfect square factors) given the values of $χ\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. 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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2601.07137
curl -X POST /api/v1/records/arxiv/2601.07137/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.07137/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'