skip to content
PSYCHO VIRTUAL

Down the Rabbit-Hole: The Low-Degree Test

/ 10 min read

This work is supported by a grant from the Mina Foundation

The Low-Degree Test (LDT) is a cornerstone in theoretical computer science, particularly in the realms of cryptography and property testing. It allows us to verify whether a function behaves like a low-degree polynomial without fully examining it, offering a powerful tool for simplifying and understanding complex mathematical structures. LDTs are foundational in many zero-knowledge protocols, where they ensure that computations can be efficiently verified with minimal information leakage.

In this post, we will first build low-degree tests that don’t work and then build a test that does work. Once we establish the basic intuition, we will conclude by walking through the original proof.

This post draws from the Alessandro Chiesa’s lecture slides1, Oded Goldreich’s lecture notes2, and the “Robust characterization of polynomials with applications to program testing”3 paper where these techniques were first discussed.

Preliminaries

First we recall the fundamental tool of property testing which is the linearity test. We define a test VlinV_{lin} for some function f:FpnFp\forall f:\mathbb{F_p}^n \to \mathbb{F_p} with the following guarantees:

  • Completeness:
fLin[Fp,n]Pr[VLinf=1]=1f \in Lin[\mathbb{F_p},n] \to Pr[V_{Lin}^f=1] =1
  • Soundness:
(f,Lin[Fp,n])δPr[VLinf=1]δ(ϵ)\triangle(f, Lin[\mathbb{F_p}, n]) \le \delta \to Pr[V_{Lin}^f=1] \le \delta(\epsilon)

Low-degree testing adds one more constraint Lin[Fp,n,d]Lin[\mathbb{F_p}, n, d] which is the total degree of the polynomial. We define low-degree as:

LD[Fp,n,d]={f:FpnFppFp[X1,..,Xn] of deg(p)f s.t. p=f}LD[\mathbb{F_p}, n, d] = \{f:\mathbb{F_p}^n \to \mathbb{F_p} | \exists p \in \mathbb{F_p}[X_1,..,X_n] \ of \ deg(p) \le f \ s.t. \ p=f\}

In the course of this post we will be working with two functions f,gf,g over the domain DFpD \to \mathbb{F_p}. We define the distance between these two functions as the fraction of the points xDx \in D where the two functions disagree:

d(f,g)={xDf(x)g(x)}Dd(f,g) = \frac{|\{x\in D|f(x)\neq g(x)\}|}{|D|}

Univariate Polynomials

First Approach

The primary focus of LDT is testing multivariate polynomials, however we will start with univariate polynomials and build our way up to more complex polynomials.

First we recall that a polynomial is defined by any d+1d+1 locations in α1,α2,αdFp\alpha_1, \alpha_2, \alpha_{d} \in \mathbb{F_p}. The goal then becomes to define the following test:

VLinf:FpFp[Fp,d]=1V_{Lin}^{f:\mathbb{F_p} \to \mathbb{F_p}}[\mathbb{F_p}, d] = 1

The naive approach is to query the ff-values α1,...,αd\alpha_1,...,\alpha_d, interpolate them so that p~(x):={(αi,f(αi))}i=1d\tilde{p}(x) := \{(\alpha_i, f(\alpha_i))\}_{i=1}^d and then check against a random point rFpr \in \mathbb{F_p} such that p~(r)=f(r)\tilde{p}(r) = f(r).

The major problem with the naive approach is its impractical query complexity when extended to multivariate polynomials.

  • In the naive approach, you query ff at dd points and then check at one additional random point rr, totaling d+1d+1 queries.

However, when dealing with multivariate polynomials this approach leads to an exponential number of queries. Recall that for a polynomial of nn-variables x1,x2,xnx_1, x_2, x_n of total degree dd, each monomial is of the form x1k1,x2k2,..,xnknx_1^{k_1}, x_2^{k_2},..,x_n^{k_n} where kk is an integer such that k1+k2+..+kndk_1 + k_2 +..+k_n \le d.

The total number of monomials is given using the multiset coefficient calculated using the Binomial Coefficient Formula, given as:

(!n!d)=!n!d(nd)!\binom{!n}{!d} = \frac{!n}{!d(n-d)!}

Which leads to a total query complexity

(n+dd)+1\binom{n + d}{d} + 1

Meaning query complexity grows exponentially with the size of nn.

Second Approach

With our first naive attempt out of the way, let’s now illustrate a second approach. In this attempt we focus on the unique structure of polynomials over finite fields, such as their behavior under addition and multiplication, and the structure provided by field operations.

In this approach, we look at the binomial coefficients and explore the concept of finite differences. For any polynomial we define the first finite difference as:

f(α)=f(α+1)f(α)\triangle f(\alpha)= f(\alpha+1) - f(\alpha)

And then for the nn-difference, we use:

nf(x)=k=0n(1)n+1(nk)f(x+k)\triangle^n f(x) = \sum_{k=0}^n(-1)^{n+1}\binom{n}{k}f(x+k)

Using this formula we can compute the finite difference up to any point d+1d+1 where the finite difference d+1f(x)=0\triangle^{d+1}f(x)=0.

ci:=(1)i+1(d+1i)Fpc_i := (-1)^{i+1}\binom{d+1}{i} \in \mathbb{F_p}

Our goal then, is to evaluate ff in terms of the finite difference between each term. If this sums to 0 then ff is of low-degree. We are looking for:

d<p f:FpFp fFpd[x]αFpi=0d+1cif(α+i)=0\forall d < p \ \forall f:\mathbb{F_p} \to \mathbb{F_p} \ f \in \mathbb{F_p}^{\le d}[x] \leftrightarrow \forall{\alpha} \in \mathbb{F_p} \sum_{i=0}^{d+1} c_i \cdot f(\alpha+i)=0

To see how this works, take for example a dd-degree 0 polynomial:

(c0,c1)=(1,1)f(α)+f(α+1)=0(c_0, c_1)=(-1,1) \to -f(\alpha) + f(\alpha+1)=0

Compared to a dd-degree 1 polynomial:

(c0,c1,c2)=(1,2,1)f(α)+2f(α+1)f(α+2)=0(c_0, c_1, c_2)=(-1,2,-1) \to -f(\alpha) + 2f(\alpha+1) - f(\alpha+2)=0

Now our verifier Vf:FpFpV^{f:\mathbb{F_p} \to \mathbb{F_p}} proceeds with the following steps:

  1. Sample rFpr \leftarrow \mathbb{F_p}
  2. Query ff at r,r+1,..,r+(d+1)r, r+1,.., r+(d+1)
  3. Check that i=0d+1cif(r+i)=0\sum_{i=0}^{d+1} c_i \cdot f(r+i)=0

However, with this approach we still have a major problem. In this case our queries are spaced linearly instead of randomly, and for some cases this test will accept with either a very high probability or always. Especially when the field’s characteristic pp is small or pdp ≤ d — the coefficients cic_i in the test can become zero or behave unexpectedly, causing the test to fail.

Third Approach

In our third and final approach, we are going to introduce one additional random field element hFph \in \mathbb{F_p} which will ensure our test behaves correctly. We characterize this with the following approach.

d<p f:FpFp fFpd[x]α,hFpi=0d+1cif(α+ih)=0\forall d < p \ \forall f:\mathbb{F_p} \to \mathbb{F_p} \ f \in \mathbb{F_p}^{\le d}[x] \leftrightarrow \forall{\alpha,h} \in \mathbb{F_p} \sum_{i=0}^{d+1} c_i \cdot f(\alpha+i \cdot h)=0

Now, when the direction is \leftarrow we set h=1h=1 and invoke our original lemma. And when the direction is \to, we fix α,hFp\alpha,h \in \mathbb{F_p} and consider the case when g(x):=f(αx+h)g(x) := f(\alpha x+h).

This adjustment effectively randomizes the input to ff along lines in the field, parameterized by α\alpha and hh, which helps to overcome the limitations caused by the field’s characteristic. By introducing hh, the test evaluates ff not just along fixed increments (as in +1,α,α+1,)+1,…\alpha,\alpha+1,…), but along any arithmetic progression in Fp\mathbb{F_p}. Now our local constraints increase from Fp=p|\mathbb{F_p}|=p to Fp2=p2|\mathbb{F_p}|^2=p^2.

This results in a total low-degree test with query complexity O(d3)O(d^3) independent of nn, meaning that unlike the previous tests this test will extend to multivariate polynomials with no change.

Multivariate Polynomials

Now that we have a good starting point with univariate polynomials, we will apply the same techniques to multivariate polynomials. Even though the type of polynomials used changes, our main equation only changes very slightly. We introduce a vector size nn and as well as variables x1,...,xnx_1,...,x_n.

d<p f:FpnFp fFpd[x1,..,xn]α,hFpni=0d+1cif(α+ih)=0\forall d < p \ \forall f:\mathbb{F_p}^n \to \mathbb{F_p} \ f \in \mathbb{F_p}^{\le d}[x_1,..,x_n] \leftrightarrow \forall{\alpha,h} \in \mathbb{F_p}^n \sum_{i=0}^{d+1} c_i \cdot f(\alpha+i \cdot h)=0

The test itself is also similar, for the verifier VRSf:FpnFpV_{RS}^{f:\mathbb{F_p}^n \to \mathbb{F_p}}, we run the following algorithm:

  1. Sample r,sFpnr,s \leftarrow \mathbb{F_p}^n
  2. Query ff at r,r+s,..,r+(d+1)sr,r+s,..,r+(d+1) \cdot s
  3. Check that i=0d+1cif(r+is)=0\sum_{i=0}^{d+1} c_i \cdot f(r + i \cdot s) =0

And for soundness we get:

Pr[VRSf=0]min{14(d+2)2,12(f,Fpd[x1,..,xn])}\Pr[V_{RS}^f=0] \ge \min \{\frac{1}{4 \cdot (d+2)^2}, \frac{1}{2} \cdot \triangle(f, \mathbb{F_p}^{\le d}[x_1,..,x_n])\}

A Robust Characterization of Polynomial Functions

Now that we have established the basics, we are prepared to delve into the actual proof of the robust characterization of polynomial functions. The following lemmas and proofs are drawn directly from the original Rubinfeld and Sudan test3 and demonstrates that if a function passes a specific low-degree test with high probability, then it is close to a degree-dd polynomial.

Proof Outline

Distance Bound: Let δ0=12(d+2)2\delta_0 = \frac{1}{2(d+2)^2}.

Mapping: Consider a function P:FpmFpP: \mathbb{F_p}^m \to \mathbb{F_p}.

We define the error probability δ\delta as:

δ=Prα,hFpm[P(α)i=1d+1ciP(α+ih)]δ0,\delta = \Pr_{\alpha,h \in \mathbb{F_p}^m} \left[P(\alpha) \neq \sum_{i=1}^{d+1} c_i P(\alpha + i h)\right] \leq \delta_0,

where ciFpc_i \in \mathbb{F_p} are fixed coefficients, and the operations are performed in Fp\mathbb{F_p}.

Our goal is to show that if this condition is satisfied, then there exists a degree-dd polynomial g:FpmFpg: \mathbb{F_p}^m \to \mathbb{F_p} that is 2δ2\delta-close to PP, meaning they agree on at least 12δ1 - 2\delta fraction of the inputs.

Lemma 6

If δδ0\delta \leq \delta_0, then there exists a degree-dd polynomial g:FpmFpg: \mathbb{F_p}^m \to \mathbb{F_p} such that PP and gg agree on more than 12δ1 - 2\delta fraction of the inputs in Fpm\mathbb{F_p}^m.

Proof:

Suppose, for contradiction, that PP is not 2δ2\delta-close to any degree-dd polynomial. This means that for every degree-dd polynomial qq, we have:

PrxFpm[P(x)q(x)]>2δ.\Pr_{x \in \mathbb{F_p}^m}[P(x) \neq q(x)] > 2\delta.

Let E={xFpmP(x)q(x)}E = \{ x \in \mathbb{F_p}^m \mid P(x) \neq q(x) \}. Then, E>2δFpm|E| > 2\delta |\mathbb{F_p}^m|.

Consider the probability that PP fails the test at a random (α,h)(\alpha, h):

Prα,h[P(α)i=1d+1ciP(α+ih)]EFpm(1(1EFpm)d+1).\Pr_{\alpha,h} \left[ P(\alpha) \neq \sum_{i=1}^{d+1} c_i P(\alpha + i h) \right] \geq \frac{|E|}{|\mathbb{F_p}^m|} \left( 1 - \left(1 - \frac{|E|}{|\mathbb{F_p}^m|}\right)^{d+1} \right).

Since E/Fpm>2δ|E| / |\mathbb{F_p}^m| > 2\delta, this lower bounds the failure probability:

Prα,h[P(α)i=1d+1ciP(α+ih)]>2δ(1(12δ)d+1).\Pr_{\alpha,h} \left[ P(\alpha) \neq \sum_{i=1}^{d+1} c_i P(\alpha + i h) \right] > 2\delta \left(1 - (1 - 2\delta)^{d+1}\right).

For small δ\delta, this expression exceeds δ\delta, contradicting the assumption that δδ0\delta \leq \delta_0. Therefore, there must exist a degree-dd polynomial gg such that:

PrxFpm[P(x)=g(x)]12δ.\Pr_{x \in \mathbb{F_p}^m}[P(x) = g(x)] \geq 1 - 2\delta.

Lemma 7

For all αFpm\alpha \in \mathbb{F_p}^m,

PrhFpm[g(α)=i=1d+1ciP(α+ih)]12(d+1)δ.\Pr_{h \in \mathbb{F_p}^m} \left[ g(\alpha) = \sum_{i=1}^{d+1} c_i P(\alpha + i h) \right] \geq 1 - 2(d+1)\delta.

Proof:

Since PP and gg agree on at least 12δ1 - 2\delta fraction of the inputs, the probability that P(α)g(α)P(\alpha) \neq g(\alpha) is at most 2δ2\delta. Similarly, for each ii, the probability that P(α+ih)g(α+ih)P(\alpha + i h) \neq g(\alpha + i h) is at most 2δ2\delta.

For fixed α\alpha, the probability over hh that any of the P(α+ih)P(\alpha + i h) differ from g(α+ih)g(\alpha + i h) is at most (d+1)×2δ=2(d+1)δ(d+1) \times 2\delta = 2(d+1)\delta.

Therefore, the probability that all P(α+ih)=g(α+ih)P(\alpha + i h) = g(\alpha + i h) for i=1,,d+1i = 1, \ldots, d+1 is at least 12(d+1)δ1 - 2(d+1)\delta.

When P(α)=g(α)P(\alpha) = g(\alpha) and P(α+ih)=g(α+ih)P(\alpha + i h) = g(\alpha + i h) for all ii, we have:

g(α)=P(α)=i=1d+1ciP(α+ih)=i=1d+1cig(α+ih).g(\alpha) = P(\alpha) = \sum_{i=1}^{d+1} c_i P(\alpha + i h) = \sum_{i=1}^{d+1} c_i g(\alpha + i h).

Therefore,

Prh[g(α)=i=1d+1ciP(α+ih)]12(d+1)δ.\Pr_{h} \left[ g(\alpha) = \sum_{i=1}^{d+1} c_i P(\alpha + i h) \right] \geq 1 - 2(d+1)\delta.

Lemma 8

For all α,hFpm\alpha, h \in \mathbb{F_p}^m, if δ12(d+2)2\delta \leq \frac{1}{2(d+2)^2}, then

i=0d+1cig(α+ih)=0.\sum_{i=0}^{d+1} c_i g(\alpha + i h) = 0.

Proof:

From Lemma 7, for each fixed α\alpha, the probability over hh that

g(α)=i=1d+1ciP(α+ih)g(\alpha) = \sum_{i=1}^{d+1} c_i P(\alpha + i h)

is at least 12(d+1)δ1 - 2(d+1)\delta.

Similarly, since PP and gg agree on all but a 2δ2\delta fraction of points, the probability over hh that P(α+ih)=g(α+ih)P(\alpha + i h) = g(\alpha + i h) for all ii is at least 12(d+1)δ1 - 2(d+1)\delta.

Combining these, the probability that both g(α)=i=1d+1ciP(α+ih)g(\alpha) = \sum_{i=1}^{d+1} c_i P(\alpha + i h) and P(α+ih)=g(α+ih)P(\alpha + i h) = g(\alpha + i h) for all ii is at least:

14(d+1)δ.1 - 4(d+1)\delta.

Thus, the probability that

g(α)=i=1d+1cig(α+ih)g(\alpha) = \sum_{i=1}^{d+1} c_i g(\alpha + i h)

is at least 14(d+1)δ1 - 4(d+1)\delta.

Since δ12(d+2)2\delta \leq \frac{1}{2(d+2)^2}, we have 4(d+1)δ2(d+1)(d+2)2<14(d+1)\delta \leq \frac{2(d+1)}{(d+2)^2} < 1, so the probability is positive.

Now, consider the polynomial:

F(α,h)=i=0d+1cig(α+ih).F(\alpha, h) = \sum_{i=0}^{d+1} c_i g(\alpha + i h).

This is a polynomial in α\alpha and hh of degree at most dd in each variable. The set of (α,h)(\alpha, h) where F(α,h)0F(\alpha, h) \neq 0 has measure less than 1, and since Fp\mathbb{F_p} is a finite field, a nonzero polynomial of total degree less than pp can vanish on at most a fraction proportional to its degree over pp.

Given that F(α,h)F(\alpha, h) vanishes on a positive fraction of Fpm×Fpm\mathbb{F_p}^m \times \mathbb{F_p}^m, and pp is sufficiently large, it must be identically zero. Therefore,

i=0d+1cig(α+ih)=0for all α,hFpm.\sum_{i=0}^{d+1} c_i g(\alpha + i h) = 0 \quad \text{for all } \alpha, h \in \mathbb{F_p}^m.

This equality implies that gg satisfies a specific linear recurrence relation, reinforcing that gg is indeed a degree-dd polynomial.

Conclusion

By the above lemmas, we have shown that if PP passes the low-degree test with error probability δδ0\delta \leq \delta_0, then there exists a degree-dd polynomial gg such that PP and gg agree on at least 12δ1 - 2\delta fraction of the inputs. Moreover, gg satisfies the recurrence relation i=0d+1cig(α+ih)=0\sum_{i=0}^{d+1} c_i g(\alpha + i h) = 0 for all α,hFpm\alpha, h \in \mathbb{F_p}^m, confirming its degree bound.

Footnotes

  1. A. Chiesa Lecture Notes on Low Degree Tests https://ic-people.epfl.ch/~achiesa/fopp-course.html

  2. O. Goldreich Lecture Notes on Low Degree Tests https://www.wisdom.weizmann.ac.il/~oded/PDF/pt-low.pdf

  3. R. Rubinfeld and M. Sudan. Robust characterization of polynomials with applications to program testing. SIAM Journal on Computing, 25(2), pages 252–271, 1996. https://people.csail.mit.edu/ronitt/papers/rs.pdf 2