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 for some function with the following guarantees:
- Completeness:
- Soundness:
Low-degree testing adds one more constraint which is the total degree of the polynomial. We define low-degree as:
In the course of this post we will be working with two functions over the domain . We define the distance between these two functions as the fraction of the points where the two functions disagree:
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 locations in . The goal then becomes to define the following test:
The naive approach is to query the -values , interpolate them so that and then check against a random point such that .
The major problem with the naive approach is its impractical query complexity when extended to multivariate polynomials.
- In the naive approach, you query at points and then check at one additional random point , totaling queries.
However, when dealing with multivariate polynomials this approach leads to an exponential number of queries. Recall that for a polynomial of -variables of total degree , each monomial is of the form where is an integer such that .
The total number of monomials is given using the multiset coefficient calculated using the Binomial Coefficient Formula, given as:
Which leads to a total query complexity
Meaning query complexity grows exponentially with the size of .
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:
And then for the -difference, we use:
Using this formula we can compute the finite difference up to any point where the finite difference .
Our goal then, is to evaluate in terms of the finite difference between each term. If this sums to 0 then is of low-degree. We are looking for:
To see how this works, take for example a -degree 0 polynomial:
Compared to a -degree 1 polynomial:
Now our verifier proceeds with the following steps:
- Sample
- Query at
- Check that
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 is small or — the coefficients 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 which will ensure our test behaves correctly. We characterize this with the following approach.
Now, when the direction is we set and invoke our original lemma. And when the direction is , we fix and consider the case when .
This adjustment effectively randomizes the input to along lines in the field, parameterized by and , which helps to overcome the limitations caused by the field’s characteristic. By introducing , the test evaluates not just along fixed increments (as in , but along any arithmetic progression in . Now our local constraints increase from to .
This results in a total low-degree test with query complexity independent of , 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 and as well as variables .
The test itself is also similar, for the verifier , we run the following algorithm:
- Sample
- Query at
- Check that
And for soundness we get:
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- polynomial.
Proof Outline
Distance Bound: Let .
Mapping: Consider a function .
We define the error probability as:
where are fixed coefficients, and the operations are performed in .
Our goal is to show that if this condition is satisfied, then there exists a degree- polynomial that is -close to , meaning they agree on at least fraction of the inputs.
Lemma 6
If , then there exists a degree- polynomial such that and agree on more than fraction of the inputs in .
Proof:
Suppose, for contradiction, that is not -close to any degree- polynomial. This means that for every degree- polynomial , we have:
Let . Then, .
Consider the probability that fails the test at a random :
Since , this lower bounds the failure probability:
For small , this expression exceeds , contradicting the assumption that . Therefore, there must exist a degree- polynomial such that:
Lemma 7
For all ,
Proof:
Since and agree on at least fraction of the inputs, the probability that is at most . Similarly, for each , the probability that is at most .
For fixed , the probability over that any of the differ from is at most .
Therefore, the probability that all for is at least .
When and for all , we have:
Therefore,
Lemma 8
For all , if , then
Proof:
From Lemma 7, for each fixed , the probability over that
is at least .
Similarly, since and agree on all but a fraction of points, the probability over that for all is at least .
Combining these, the probability that both and for all is at least:
Thus, the probability that
is at least .
Since , we have , so the probability is positive.
Now, consider the polynomial:
This is a polynomial in and of degree at most in each variable. The set of where has measure less than 1, and since is a finite field, a nonzero polynomial of total degree less than can vanish on at most a fraction proportional to its degree over .
Given that vanishes on a positive fraction of , and is sufficiently large, it must be identically zero. Therefore,
This equality implies that satisfies a specific linear recurrence relation, reinforcing that is indeed a degree- polynomial.
Conclusion
By the above lemmas, we have shown that if passes the low-degree test with error probability , then there exists a degree- polynomial such that and agree on at least fraction of the inputs. Moreover, satisfies the recurrence relation for all , confirming its degree bound.
Footnotes
-
A. Chiesa Lecture Notes on Low Degree Tests https://ic-people.epfl.ch/~achiesa/fopp-course.html ↩
-
O. Goldreich Lecture Notes on Low Degree Tests https://www.wisdom.weizmann.ac.il/~oded/PDF/pt-low.pdf ↩
-
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