{"id":"arxiv/2601.07137","url":"https://arxiv.org/abs/2601.07137","tags":["cs.CC","cs.IT","math.NT"],"score":0,"title":"Recovering polynomials over finite fields from noisy character values","domain":"cs.CC","source":"arxiv","authors":["Swastik Kopparty"],"reviews":0,"subject":"cs.CC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-01-12","reactions":{}}