Metraipolis › archive › dc_29cad70aedef

On derandomizing the line-point low-degree test — arXiv:2611.09183

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.09183
License (as archived)
CC0-1.0
Archived
2026-11-09T22:44:10.241Z
SHA-256 of the archived text
41c9ea7c2d87086c7e6870d05eca3de1f2a289c6e03453266b10f63c5ed787de
Stable URL of this page
https://metraipolis.com/documento/dc_29cad70aedef

How to cite

On derandomizing the line-point low-degree test — arXiv:2611.09183 — arXiv (en), https://arxiv.org/abs/2611.09183 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_29cad70aedef (Metraipolis archive dc_29cad70aedef, sha256 41c9ea7c2d87086c7e6870d05eca3de1f2a289c6e03453266b10f63c5ed787de)
BibTeX
@misc{dc29cad70aedef,
  title = {On derandomizing the line-point low-degree test — arXiv:2611.09183},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.09183},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_29cad70aedef; sha256 41c9ea7c2d87086c7e6870d05eca3de1f2a289c6e03453266b10f63c5ed787de},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.09183. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We investigate the derandomized version of the classical line-point low-degree test in the high-error regime in the bivariate setting and reveal some unexpected behavior. The classical line-point low-degree test takes an $m$-variate function $f$ over a finite field $\mathbb{F}_q$, queries it along a random line and accepts if the restriction of the function to this line is a low-degree polynomial. The high-error version of (the analysis of) this test asserts that if $f$ has at least $\epsilon$ expected local agreement with a degree-$k$ univariate polynomial on a random line, then in fact $f$ is non-trivially close to some degree-$k$ $m$-variate polynomial even as $\epsilon$ approaches $0$ (provided $q$ is sufficiently large compared to $k$ and $1/\epsilon$). The derandomized version of the problem asks if the same holds when the line is not chosen uniformly over all possible lines but rather from a small this http URL this paper we explore the bivariate case ($m=2$). We show, somewhat surprisingly, that there exists a function $f\colon \mathbb{F}_q^2 \to \mathbb{F}_q$ and a set of lines $\mathcal{L}$ in $\mathbb{F}_q^2$ of size nearly $q^{3/2}$ such that on every line in $\mathcal{L}$, $f$ has agreement $\approx 1/2$ on average with some univariate polynomial of degree $k=\sqrt{q}/2$ and yet $f$ is $1 - O(q^{-1/2})$ far from every polynomial of degree $O(k)$. On the positive side, we show that once the field size $q$ is at least $k^2/(\epsilon)^{O(1)}$ such examples disappear and we can get sets of lines of size $O(q/\epsilon^{O(1)})$ on which the low-degree test has a high-error analysis. On the way to our positive result, we show a new high-degree version of the classical two-direction Polishchuk--Spielman divisibility lemma.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.IT, nuovi lavori del giorno).
Categorie arXiv: Computational Complexity (cs.CC) ; Information Theory (cs.IT).
Pagina del lavoro: https://arxiv.org/abs/2611.09183 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-09T22:36:47.311Z dalla pagina https://arxiv.org/list/math.IT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).