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 set. Derandomized analyses of low-degree tests play a crucial role in obtaining near-linear sized PCPs. In 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/\text{poly}(\epsilon)$ 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. It deals with finding a low-degree global root $Z = U(X,Y)$ of a trivariate polynomial $Q(X,Y,Z)$, based on restrictions of $Q$ to lines in $r > \deg_Z(Q)$ different directions (generalizing the original $r = 2$ and $\deg_Z(Q) = 1$ case). Specifically, it states that if $Q$ has a low-degree root $Z = U_{a,b}(X)$ for all lines $Y = aX + b$ in each of those $r$ directions, then $Q$ has a low-degree global root $Z = U(X,Y)$. This high degree Polishchuk--Spielman lemma is proved by a new technique: using simultaneous Hensel lifting of "consistent" roots on many parallel lines.

Our negative result addresses one of the big challenges in analyzing low-degree tests, namely the rarity of interesting counterexamples that offer concrete barriers.