18.408 F2022 Lectures 7–8: Low Degree Testing

18.408 Topics in Theoretical Computer Science Fall 2022 Lectures 7,8 Dor Minzer Last time we presented the sum-check protocol which enabled us to test whether a given assignment A0 : Fm q → Fq that is promised to be a low degree polynomial satisfies a given equation or not, using only poly(log n) many queries. Today, we will introduce representations of low degree polynomials that enable one to test that a given table of values A0 indeed represents a low degree polynomial using only constantly many queries. In subsequent lectures we combine this with the sum check protocol and construct a PCP with poly(log n) many queries. 1 Low Degree Testing Throughout this lecture, we are working over the field Fq and with the parameters m, d ∈ N, where d is the total degree and m is the number of variables. 1.1 The Line versus Point Scheme Suppose f : Fm q → Fq is a polynomial of total degree at most d. The most natural encoding of f is its table of values; this encoding however, is not good enough for our purposes since it doesn’t admit a tester with constantly many queries. A natural idea thus is to consider the table of restriction to “higher dimensional” objects than points. For example, one may consider the table of restrictions of f to lines. m m Definition 1.1. We define S1 (Fm q ) to be the set of all lines in Fq . That is, S1 (Fq ) is the collection of sets of m the form La,b = { at + b | t ∈ Fq }, for a, b ∈ Fq . Note that if L ∈ S1 (Fm q ), then the restriction f |L is a univariate polynomial of degree at most d. Indeed, if the line L is parameterized as L = { at + b | t ∈ Fq }, the restriction can be thought of as the univariate function f |L (t) = f (a + tb), which has degree at most d. Thus, to encode f we can specify its table of values as well as the table of restrictions of f to all lines. Namely, we can encode a polynomial f by m B0 : Fm q → Fq defined as B0 (x) = f (x), as well as B1 : Lines(Fq ) → {degree d univariate polynomials} defined as B1 [L] = f |L . First, we consider the size of the encoding. Letting N = q m , the number of points in Fm q is N , and the 2 (since a line is specified by two points), hence the size of the encoding is number of lines in Fm is about N q about N 2 + N , which is polynomial in the size of the original object; this is good enough for us. Second, we discuss the local test corresponding to this encoding. The most natural test associated with this scheme is the line versus point test. In this context, our input consists of two tables B0 and B1 (which are supposed encodings of a low-degree polynomial f ), where B0 assigns an Fq -value to each point x, and B1 assigns a univariate polynomial over Fq of degree at most d to each line in S1 (Fm q ). The test is: m 1. Sample a point x ∈ Fm q randomly and take a random line L ∈ S1 (Fq ) containing x. 1 2. Query B0 (x) and B1 [L]. 3. Check that B1 [L](x) = B0 (x). The completeness of this test is clear. That is, if B0 , B1 are the tables of some polynomial f : Fm q → Fq of degree at most d, then the test passes with probability 1. What about the soundness? Theorem 1.2. Suppose that B0 , B1 are tables that pass the line versus point test with probability at least 1 − ε. Then there exists a polynomial f : Fm q → Fq of total degree d, such that Pr [f (x) = B0 (x)] > 1 − O(ε), Pr x∈Fm q L∈S1 (Fm q ) [f |L ≡ B1 [L]] > 1 − O(ε). In words, if the test passes with probability close to 1, then the tables B0 and B1 are close to the tables of some low-degree polynomial f . This regime of parameters is often called the “99% regime”, since it makes a structural assertion on the assignment in the case that the test passes with probability close to 1. Such results are typically easier to prove, and they have been indeed utilized in early PCP constructions. However, such results cannot directly be used towards constructing PCPs with small error (i.e. large gap between the completeness and the soundness), and for that one needs to address the so-called “1%” regime. Here, one assumes that the test passes with probability at least ε (which is small but bounded away from 0), and wants to conclude that the assignments B0 , B1 still must have a global structure. In this regime, we have the following theorem: Theorem 1.3. There are absolute constants C > 0 and c > 0 such that the following holds. Suppose that C C B0 , B1 are tables that pass the line versus point test with probability at least ε, where ε > d qm . Then c there exists a polynomial f : Fm → F of total degree d, such that q q Pr [f (x) = B0 (x)] > Ω(ε), x∈Fm q Pr L∈Lines(Fm q ) [f |L ≡ B1 [L]] > Ω(ε). The known proofs of Theorem 1.3 are quite complicated, and we will not present them here. Part of the issue is that the structure offered to us by lines, and in particular the bipartite graph between lines and points associated with the test, lacks enough “combinatorial structure” and “expansion”. Indeed, the proof of Theorem 1.3 is heavily algebraic. To circumvent this, we will consider a different (but similar in spirit) encoding schemes of low degree polynomials that are easier to analyze. 1.2 The Plane versus Line and Plane versus Point Schemes A natural idea of the previous scheme is to consider, instead of lines, higher dimensional affine subspaces. m Definition 1.4. We denote by Sr (Fm q ) the collection of all affine subspaces of Fq of dimension r. Whenever q and m are clear from context, we will drop them from the notation and simply write Sr . Note that letting N = q m , we have that |Sr | ≈ N r , thus as long as r is constant, we can afford ourselves to use tables for Sr in our encodings. In this way, given a degree d polynomial f : Fm q → Fq , we can define Br : Sr → {total degree d polynomial over r variables} as Br [P ] = f |P for each P ∈ Sr . We will refer to this as the r-dimensional encoding of f . For concreteness, we shall focus on the case that r = 2, in which case S2 (Fm q ) consists of all of the affine planes in Fm . This will be good enough for our purposes, but we remark that there is some merit in q 2 considering higher r. First, we will have to do so in the analysis of the test for r = 2, and second, better analysis is known for larger r. Still, our focus shall be on r = 2. So, if we have our (supposed) assignments B0 , B1 to points and lines and B2 to planes. How shall we go about testing them? The first option is the plane versus point test: m 1. Sample a point x ∈ Fm q randomly and take a plane P ∈ S2 (Fq ) that contains x. 2. Query B0 (x) and B2 [P ]. 3. Check that B2 [P ](x) = B0 (x). The second option is the plane versus line test: m 1. Sample a line L ∈ S1 (Fm q ) randomly and take a plane P ∈ S2 (Fq ) that contains L. 2. Query B1 [L] and B2 [P ]. 3. Check that B2 [P ]|L ≡ B1 [L]. And yet, there are third and fourth options. Both go under the name “the plane versus plane test”, but they vary in the dimension of space these planes intersect in. The first variant is the Plane versus Plane test on planes that intersect on a line: 0 m 1. Sample a line L ∈ S1 (Fm q ) randomly and take two plane P, P ∈ S2 (Fq ) that contain L. 2. Query B2 [P ] and B2 [P 0 ]. 3. Check that B2 [P ]|L ≡ B2 [P 0 ]|L . The second variant is the Plane versus Plane test on planes that intersect on a point: 0 m 1. Sample a point x ∈ S0 (Fm q ) randomly and take two plane P, P ∈ S2 (Fq ) that contain x. 2. Query B2 [P ] and B2 [P 0 ]. 3. Check that B2 [P ](x) = B2 [P 0 ](x). It turns out that all of these tests work, roughly equally well, in the sense that a result analogous to Theorem 1.3 holds for each one of the, albeit with somewhat different parameters. In fact, one can reduce the analysis of any one of them to any other; we will see some of these connections here, and some of them in the problem set. For the purposes of our future PCP application, we will have to analyze the plane versus point and plane versus plane tests; in particular, we will prove the following statement: Theorem 1.5. Suppose that B0 , B2 are tables for the plane versus point test with probability at least ε > d2 . Then there exists a polynomial f : Fm q → Fq of total degree d, such that q 1/10 Pr [B0 (x) = f (x)] > ε − x∈Fm q md . q 1/10 In words, theorem 1.5 says that if the plane versus point passes with significant probability ε, then the points table B0 agrees with a function f of degree at most d on at least ε − o(1) of the points. This formulation will be quite important for us for the purpose of this lecture, since it admits a proof by induction on m (which is the route we are going to take). For future use, we need a corollary of it, which we state now and deduce from Theorem 1.5 later in Section 2.6. 3 Theorem 1.6. Suppose that B0 , B2 are tables for the plane versus point test with probability at least ε > d2 d2 . Then for all δ > q1/10 there is k 6 δ22 and a list of polynomials f1 , . . . , fk : Fm q → Fq of total degree q 1/10 d, such that Pr [B0 (x) = B2 [P ](x) ∧ B2 [P ] 6= fj |P ∀j] 6 3δ. x∈P ∈S2 (Fm q ) In words, we can find a short list of low-degree polynomials f1 , . . . , fk such that except for small probability, if the test passes, then it is because the plane table is consistent with one of the polynomials in the list. 2 Analysis of the Plane versus Plane Test En route to proving Theorem 1.5, we need to consider the related Plane versus Plane test on planes that intersect on lines as described earlier. This is the content of this section and where most the “action” takes place. Let m = 3, and suppose B2 : S2 (F3q ) → {total degree d polynomials in 2-variables} passes the plane versus plane test with probability at least ε. Then, in light of the formulation of Theorem 1.3, one expects to prove that there is a polynomial f : F3q → Fq of total degree at most d that agrees with B2 on Ω(ε) of the planes. This is true and will come as a byproduct of the argument we present, however for the purpose of Theorem 1.5, we need the following list-decoding statement. Theorem 2.1. Suppose that B2 is a table that pass the plane versus plane test with probability at least ε, and let δ > 2(d+1) . Then there is k 6 1δ and k polynomials f1 , . . . , fk : F3q → Fq of total degree d, such that q s   d+1 Pr B2 [P ]P ∩P 0 ≡ B2 [P 0 ]P ∩P 0 ∧ ∀j(B2 [P ] 6≡ fj ∨ B2 [P 0 ] 6≡ fj ) 6 δ + 2 . 0 3 q P,P ∈S2 (Fq ) as in the test In words, Theorem 2.1 provides a short list of polynomials f1 , . . . , fk such that all of the success of the test can be explained by it. Namely, for all but small fraction of the tests (P, P 0 ), if the test passes on planes P and P 0 , then there is some fj in the list such that fj is consistent with both B2 [P ] and B2 [P 0 ]. The main feature which of the fact that m = 3, is that two randomly chosen planes intersect on a line, proved in the following fact. 1 Fact 2.2. PrP,P 0 ∈S2 (F3q ) [dim(P ∩ P 0 ) 6= 1] 6 1 . q2 3 3 3 (q −1)(q −q) Proof. The number of planes in F3q is exactly qq2 (q 2 −1)(q 2 −q) ; here, the numerator counts the number of ways to choose 3 points that span an affine plane, and the denominator counts the number of times a given plane 3 −1 P is counted. Simplifying, this is N = q qq−1 = q(q 2 + q + 1). Thus, the number of pairs of planes is N 2 . If two planes do not intersect on a line, then they either are identical – there are N such pairs, or are parallel – there are N · (q − 1) such pairs. Indeed, they cannot intersect at a point, since if P, P 0 intersect on a point x, we can write them as P = x + L, P 0 = x + L0 for two subspaces L, L0 , and as dim(L ∩ L0 ) = dim(L) + dim(L0 ) − dim(L ⊕ L0 ) > 4 − 3 = 1 it follows that P and P 0 intersect on a line. It follows that   N + N (q − 1) 1 1 Pr dim(P ∩ P 0 ) 6= 1 = = 6 2. 2 0 3 N N q P,P ∈S2 (Fq ) 1 We remark that importantly, the analogous statement for m = r + 1 is true for r-dimensional affine subspaces of Fm q . Namely, two random r-dimensional affine subspaces of Fr+1 intersect on an r−1-dimensional affine subspace except with small probability. q Thus, the proof we presents works in this more general setting, and we will in fact use it later on in this generality. 4 2.1 The Assignment Graph Consider the graph G = (V, E) whose vertex set is S2 (F3q ), and two vertices P, P 0 ∈ V are adjacent if   B2 [P ]P ∩P 0 ≡ B2 [P 0 ]P ∩P 0 . Note that |E| > ε 1 − q12 |V |2 , so thinking of ε as bounded away from 0, the graph G is dense. We will want to study the combinatorial structure of G, and in particular show that it is roughly a union of cliques. We will then consider the cliques that are sizable, which are collections of planes that are all around consistent, and for each one of them we will construct a degree d function f that is consistent it. This will be our list. 2.2 Making G Transitive The heart of the analysis of the Plane versus Plane test is the fact that the graph G is close to being a transitive graph. Definition 2.3. A graph H = (V, E) is called transitive if there are no triple of vertices u, v, w ∈ V such that (u, v) ∈ E, (v, w) ∈ E but (u, w) 6∈ E. We show that G is nearly transitive, in the sense that we can remove a few edges from it and make it transitive. To do so, define the parameter β(H) which captures the distance of H from being transitive. Definition 2.4. Let H = (V, E) be a graph. For each non-edge (u, w) 6∈ E, define β(u, w) = Pr [(u, v) ∈ E, (v, w) ∈ E], and subsequently β(H) = max β(u, w). v∈V (u,w)6∈E We prove the following two lemmas with respect to the parameter β(H). The first lemma asserts that if β(H) is small, then one can remove a few edges from H and make it transitive. The second lemma asserts that β(G) is small. p Lemma 2.5. Given a graph H = (V, E), one can remove from it at most 2 β(H) |V |2 edges to get a graph H 0 = (V, E 0 ) which is transitive. Proof. The proof is by a iterative process. Denote β = β(H), and perform the following iterations as long as they change the graph H: √ 1. If there is v such that d(v) 6 β |V |, remove all edges adjacent to v. 2. Else, take some v ∈ V and remove all edges between neighbours of v and non-neighbours of v. It is clear that when the process terminates, the graph is transitive, and the main task is to upper √ bound the total number of edges removed by the process. Clearly, the first operation can remove at most β |V |2 edges in total. For the second operation, consider an invocation of it and denote by N (v) the set of neighbours of v, and by C(v) the connected component of v. The second operation removes edges between N (v) and C(V ) \ (N (v) ∪ {v}). Prior to the removal, define Enon = { (u, w) | w ∈ C(V ) \ (N (v) ∪ {v}), u ∈ N (v)} , Eremove = { (u, w) ∈ E | w ∈ C(V ) \ (N (v) ∪ {v}), u ∈ N (v)} . By definition of β(H), for each w such that (v, w) 6∈ E, there are at most β |V | such u ∈ N (v) that (u, w) ∈ E. Thus, |Eremove | 6 |C(V ) \ (N (v) ∪ {v})| · β |V | . 5 On the other hand, the total number of pairs u, w such that u ∈ N (v) and w 6∈ N (v) is at least d(v) · |C(V ) \ (N (v) ∪ {v})|, and since the first step of the process was not executed, we get p |Enon | > β |V | |C(V ) \ (N (v) ∪ {v})| . √ √ It follows that |Eremove | 6 β |Enon |. Thus, the total number of edges removed is at most β times the total number of pairs that were in the sets Enon , and to finish the argument we argue that each pair of vertices may appear in Enon in at most a single iteration. Indeed, if (u, w) ∈ Enon when the iteration is invoked on v, then at that point of the process w and u are in the same connected component. However, after this point there are no edges between C(v)\(N (v)∪{v}) and N (v) ∪ {v}, which means that v and w are in different connected components, and as v and u are in the same connected component at that time, it follows that u and w are in different connected components. In other words, when the pair (u, w) appears in Enon the vertices u and w are in the same connected component, and after that step they are not, hence each pair appears in Enon at most once. Thus, to prove that G is almost transitive, it suffices to prove an upper bound on β(G), and this is the content of the following lemma. Lemma 2.6. For our graph G = (V, E) above, β(G) 6 d+1 q . Proof. Consider any non-edge (P1 , P3 ) in G. Sample P2 ∈ V ; what is the probability that (P1 , P2 ) and (P2 , P3 ) are all edges? In that case, we get that either P2 is disjoint from the line P1 ∩ P3 , which happens with probability at most 1q , or else P1 ∩ P2 ∩ P3 is a point x. In that case, the point x is distributed uniformly in P1 ∩P3 , and we have that B2 [P1 ], B2 [P2 ] agree on P1 ∩ P2 and B2 [P2 ], B2 [P3 ] agree on P2 ∩ P3 , so B2 [P1 ](x) = B2 [P3 ](x). However, since (P1 , P3 ) is a non edge, B2 [P1 ]|P1 ∩P3 and B2 [P3 ]|P1 ∩P3 are two distinct degree d univariate polynomials, and hence this is the probability that they agree on a randomly chosen point from P1 ∩ P3 , which is at most dq . Summarizing, 2.5, 2.6 on G = (V, E) we may find G0 = (V, E 0 ) with E 0 ⊆ E and papplying Lemmas 2 > |E| − 2 (d + 1)/qN which is transitive. Note that a transitive graph is a union of cliques, so we may write V = C1 ∪ . . . ∪ Ck where each Ci in V is a clique. Thus, the number of edges in G0 is k
P |Ci | = |E 0 |, and we show that almost all edges of G0 are covered by large cliques. Let δ > 0 to be 2 |E 0 | i=1 chosen, and set I = { i | |Ci | > δN }. Then X |Ci | 1 X δN X 6 |Ci |2 6 |Ci | 6 δN 2 . 2 2 2 i6∈I i6∈I i6∈I Thus, we find that X |Ci | i∈I 2 s 0 2 2 > E − δN > εN − 2 ! d+1 + δ N 2. q Also, clearly |I| 6 1δ . In the rest of the argument, we will find a list of polynomials (fi )i∈I which “explain” all of the edges inside the cliques (Ci )i∈I , which finishes the proof of Theorem 2.1. 6 2.3 Interpolating a Low-degree Polynomial in Each Ci Next, we show that for each Ci , we may find a polynomial fi : F3q → Fq of total degree at most d that agrees with B2 [P ] for all P ∈ Ci . , and let i ∈ I. Then there exists a polynomial fi : F3q → Fq of total Claim 2.7. Suppose that δ > 2(d+1) q degree d such that fi |P ≡ B2 [P ] for all P ∈ Ci . Proof. Choose linearly independent vectors x, y ∈ F3q , set T = Span(x, y) and take a ∈ F3q \ T uniformly. Note that each λ ∈ Fq , the distribution of λa + T is uniform over S2 . Thus, it follows that   X |Ci | 1λa+T ∈Ci  = q > δq > 2(d + 1), E  |S2 | a,T λ∈Fq hence there are a and T such that P 1λa+T ∈Ci > 2(d + 1), and we fix such a and T . Without loss λ∈Fq of generality, we assume that T = Span(e1 , e2 ) and a = e3 , otherwise we can apply an affine linear transformation. Let Λ = { λ ∈ Fq | λa + T ∈ Ci }, and take Λ0 ⊆ Λ0 of size 2(d + 1). Note that the 1 1 probability that a randomly chosen plane is parallel to a + T is (q3 −1)(q3 −q)/(q 2 −1)(q 2 −q) 6 q 2 , so it follows that the probability that a randomly chosen plane is in C and not parallel to a + T is at least δ − q12 , and using the same technique as above we may find T 0 that intersects T on a line, such that has at least d + 1 of the affine shifts of T 0 in C. That is, there are b ∈ F3q and T 0 such that b 6∈ T 0 , dim(T ∩ T 0 ) = 1 and Γ ⊆ Fq of size d + 1 such that {γb + T 0 }γ∈Γ ⊆ Ci . By applying linear transformations again we may assume b = e2 and T 0 = Span(e1 , e3 ). We will show, using interpolation, that there is fi : F3q → Fq of total degree at most 2d that agrees with B2 [γb + T 0 ] for all γ ∈ Γ, we will then argue that fi must agree with B2 [λa + T ] for all λ ∈ Λ0 , and then that fi must agree with B[P ] for all P ∈ Ci . Finally, we will show that the degree of fi must be in fact at most d. Q y−γ 0 Let `γ (y) = γ−γ 0 , and define γ 0 ∈Γ\{γ} fi (x, y, z) = X `λ (y)B2 [γa + T ](x, z). γ∈Γ0 Clearly, fi has degree at most |Γ| + d − 1 6 2d and fi |γb+T 0 = f (x, γ, z) = B2 [γb + T 0 ](x, z) for γ ∈ Γ0 . Thus, fi agrees with all {γb + T 0 }γ∈Γ , and additionally the individual degree of y in fi is at most d. Fix λ ∈ Λ0 and consider the plane λa + T . Within this plane, consider for each α the line `α,λ defined by x = α, z = λ. Note that the line `α,λ intersects each one of the planes {γb + T 0 } at a point p = (α, γ, λ) which is inside (λa + T ) ∩ (γb + T 0 ), and hence fi (p) = B[γb + T 0 ](p) = B[λa + T ](p), so we get that fi |`α,λ and B[λa + T ]|`α,λ agree on all points (α, γ, λ) for γ ∈ Γ, which constitute at d + 1 points on `α,λ . Since these are two degree d polynomials, we conclude that they must be the same, hence fi agrees with B[λa + T ] on all lines `α,λ and therefore fi |λa+T ≡ B[λa + T ] for all λ ∈ Λ0 . Next, note that any plane P is either parallel to λa + T or intersects it in a line. For P ∈ Ci that intersect it on a line, we get that B2 [P ] and B2 [λa + T ] agree on the intersection line for all λ ∈ Λ0 , and as fi and 7 B2 [λa + T ] agree, we get that B2 [P ] and fi agree on ∪λ∈Λ0 (λa + T ) ∩ P . As this set has size |Λ0 | q, we conclude that fi |P and B2 [P ] agree on at least 2(d + 1)q points p ∈ P , hence Pr [fi |P (p) = B2 [P ](p)] > p∈P 2(d + 1) 2(d + 1)q = , 2 q q and by the Schwarz-Zippel lemma, as the degrees of fi |P , B2 [P ] are both are most 2d, it follows that fi |P ≡ B2 [P ]. Thus, we conclude that fi |P and B2 [P ] agree on all planes that are not parallel to T . For planes parallel to T , say P 0 = b + T ∈ Ci , sampling P = w + T 0 ∈ S2 we get that with probability 0 > 1 − 1/q it intersects P 0 in  a line;  conditioned on that and looking at the shifts λw + T we get as before that in expectation, at least δ − 1q q > 2d + 1 of them are in Ci . Thus, we can find w, T 0 such that at least 2d + 1 of λ ∈ Fq , we have λw + T 0 ∈ Ci . Then get that B2 [P 0 ] and B2 [λw + T 0 ] agree on P 0 ∩ (λw + T 0 ) for these λ’s, hence we get that fi |P 0 and B2 [P 0 ] agree on at least (2d+1)q points, and again by Schwarz-Zippel B2 [P 0 ] ≡ fi |P 0 . Finally, we argue that fi has degree at most d. Suppose this is not the case, and consider monomial m 1 x y m2 z m3 of maximal degree, and furthermore take xm1 y m2 z m3 of that degree that maximizes m2 . Choosing a random plane amounts to looking at all points (x, y, z) such that ax + by + cz = e for randomly chosen (a, b, c) 6= 0 and uniformly chosen e ∈ Fq . With probability > 1 − 1q we have b 6= 0, so we can choose a value for b so that under the remaining probability over a, c, d, we have that this plane is in Ci with probability at least δ − 1q . Then we can write this as y = − ab x − cb y + eb , and the monomial we are inspecting yields am2 (−1)m2 m2 xm1 +m2 z m3 + other monomials. b We look at the function fi (x, − ab x − cb y + db , z), and in particular at the coefficient of xm1 +m2 z m3 as a m function of a, c, e. Then xm1 y m2 z m3 gives us (−1)m2 abm22 , and no other monomial can give this power of a 0 0 0 (indeed, this could only come from a monomial xm1 y m2 z m3 such that m01 + m02 + m03 = m1 + m2 + m3 and m01 = m1 , m02 > m2 , but we chose the monomial to maximize m2 so that then m02 = m2 , m01 = m1 and m03 = m3 ), so the coefficient of xm1 +m2 z m3 is a polynomial in a, c, e of degree at most 2d, hence choosing the values of a, c, e randomly, it is non-zero with probability at least 1 − 2d q . With probability at 1 2d+1 least δ − q > q the chosen plane is in Ci , and as the sum of these two probabilities exceeds 1, it means that there is a plane P specified by the equation ax + by + cz = e in Ci such that the monomial xm1 +m2 z m3 appears in fi |P , but then B2 [P ] = fi |P has degree larger than d, and contradiction. 2.4 Proof of Theorem 1.5 for m = 3 Having established Theorem 2.1, we can now prove Theorem 1.5 for m = 3. The proof uses the connection between the plane versus plane and the plane versus point test we earlier eluded to. Theorem 2.8. Suppose that B0 , B2 are tables that pass the plane versus point test with probability at least d2 ε > q1/10 . Then there exists a polynomial f : F3q → Fq of total degree d, such that Pr [f (x) = B0 (x)] > ε − x d q 1/10 . Proof. We first observe a connection between the plane versus plane test and the plane versus point test. Namely, we argue that if B2 and B0 pass the plane versus point test with probability at least ε, then B2 8 3 passes the plane versus plane test with probability at least ε2 − d+1 q . Indeed, sample x ∈ Fq and two planes P1 , P2 independently that contain x. Then        2   2 1 1 = > 1 1 > ε2 . E E E E E B[P1 ](x)=B0 (x) B[P2 ](x)=B0 (x) B[P ](x)=B0 (x) B[P ](x)=B0 (x) x x,P1 ,P2 x P 3x P 3x Thus, note that sampling P1 , P2 that contain a common line means that P1 , P2 intersect on a line `, and so we get that " # X 1B[P1 ](x)=B0 (x) 1B[P2 ](x)=B0 (x) > qε2 , E `,P1 ,P2 x∈` meaning that with probability at least ε2 − d+1 q , B[P1 ] and B[P2 ] agree on at least d + 1 of the points in `, in which case they are identical by Schwarz-Zippel. Overall, B2 passes the plane versus plane test with probability at least ε2 − d+1 q . C Take δ = dqc for C, c > 0 to be determined, and take all polynomials f1 , . . . , fk : F3q → Fq that agree 1 with B2 [P ] for at least δ fraction of planes; note that by Claim 2.12 we have k 6 δ2 −d/q 6 δ22 . We now define Wi = { P | fi |P ≡ B2 [P ]} , S and argue that the probability the plane versus point test picks a plane outside W := ki=1 Wi but passes is very small. To see that, define an assignment B20 to the planes such that B20 [P ] = B2 [P ] if P 6∈ W , and for each P ∈ W we choose B20 [P ] to be a randomly chosen degree d polynomial over P . By standard probabilistic arguments, after this re-randomization no degree d polynomial agrees with B20 on more than δ+ 10 d log(q q d3 ) 6 11δ fraction of the planes P , and we fix such randomization. We claim that this randomization √ implies that the success probability of the test is at most 10 δ. Indeed, otherwise by the above connection we would be able to conclude that B20 passes the plane versus plane test with probability at least 99δ, and by Theorem 2.1 we can find a function degree d function f : F3q → Fq that agrees with B20 for at least 50δ of the planes, which contradicts the property of the randomization. This means that prior to the randomization, √   Pr [f (x) = B2 [P ](x) ∧ ∀jfj |P 6≡ B2 [P ]] 6 Pr f (x) = B20 [P ](x) 6 10 δ. x∈P ∈S2 (F3q ) x∈P ∈S2 (F3q ) The following claim finishes the proof.   1/3 √ 100ε 100 δ Claim 2.9. For η = max , ε , there is j such that Prx∈F3q [fj (x) = B0 (x)] > ε − η. q2 δ2 Proof. Assume otherwise, so that the set X  j = { x | fj (x) = B0 (x)} contains at most ε − η elements for P each j. By the assumption on the test, EP 1B0 (x)=B2 [P ](x) > εq 2 , so by Claim 2.10 with probability x∈P P at least η over P , 1B0 (x)=B2 [P ](x) > (ε − η)q 2 . However, if we choose P at random, then by Claim 2.11 x∈P and the union bound we have |P ∩ Xj | 6 (ε − 50η)q 2 for all j except with probability q2kεη2 6 q2 η2ε2 δ2 . Thus with probability at least η − q2 η2ε2 δ2 > η2 both events hold together. In this case we get that fj |P 6≡ B2 [P ] P for all j, as otherwise we would have that |P ∩ Xj | = 1B0 (x)=B2 [P ](x) . In conclusion, we get that with x∈P P probability at least η2 we have that 1B0 (x)=B2 [P ](x) > (ε − η)q 2 and fj |P 6≡ B2 [P ], and so x∈P Pr x∈P ∈S2 (F3q ) [B0 (x) = B2 [P ](x), fj |P 6≡ B2 [P ] ∀j] > 9 √ η · (ε − δ) > 10 δ, 2 and contradiction. d To finish the proof we choose δ = ε2 q1/5 and η = 2.4.1 d . q 1/10 Auxiliary Claims In this section we prove auxiliary claims that were used in the proof of Theorem 2.8. The first one is an averaging argument:   P 2 Claim 2.10. PrP 1B0 (x)=B2 [P ](x) > (ε − δ)q > δ. x∈P P Proof. The expectation of x∈P 1B0 (x)=B2 [P ](x) is at least εq 2 , and it is never more than q 2 , so letting z denote the probability in question, we get that zq 2 + (1 − z)(ε − δ)q 2 > εq 2 , hence zq 2 > δq 2 , and so z > δ. The second is a sampling lemma, saying that a random plane P samples points well: Claim 2.11. Let X ⊆ F3q be a set, then # 1 |X| |X| 2 +q δ 6 2 2 3 Pr |P ∩ X| > q P q δ Fq F3q " 2 Proof. Write a randomly chosen plane as P = {x1 , . . . , xq2 }, denote Zi = 1xi ∈X , and note that |P ∩ X| = q2 P Zi . By linearity of expectation, EP [|P ∩ X|] = q 2 |X| . Also, we note that for all i 6= j, the points xi , xj |F3q | i=1 are distributed uniformly over tuples of distinct points in F3q × F3q . Thus, h i X   |X| |X| − 1 2 2 |X| 2 |X| + + q 2 (q 2 − 1) 3 , E |P ∩ X| = q E 1xi ,xj ∈X 6 q 3 3 Fq Fq Fq F3q − 1 P P i6=j  2 h i 2 |X| which yields EP |P ∩ X|2 6 q 2 |X| + q . Thus var(|P ∩ X|) 6 q 2 |X| , and by Chebyshev’s |F3q | |F3q | |F3q | inequality the left hand side of the claim is at most " Pr P # q 2 |X| |X| 1 |X| |F3q | |P ∩ X| − q 2 3 > q 2 δ 6 4 2 6 2 2 3 . q δ q δ Fq Fq The third claim is a list decoding size bound, and we prove it in a rather general form. In our case, the code will be the planes code, in which a polynomial f is encoded by its table of restrictions; this code has relative distance at least dq √ Claim 2.12. Suppose C is an error correcting code over Fnq with relative distance 1 − s, and let δ > s. When for every w ∈ Fnq , the number of codewords c ∈ C such that w and c agree on at least δn coordinates, is at most δ21−s . 10 Proof. Let c1 , . .. , ck ∈ C be all codewords that agree with w on at least δ fraction of coordinates. Then we  have that Ei∈[k] Ex∈[n] 1ci (x)=w(x) > δ, so by Cauchy-Schwarz #2 " δ2 6 E x∈[n]   E 1ci (x)=w(x) i∈[k] # " 6 E x∈[n]  E i∈[k] 1ci (x)=w(x) 2   k X X 1 1 = E  2 1ci (x)=w(x)=cj (x) . 1ci (x)=w(x) + 2 k x∈[n] k i=1 i6=j h i Note that for i 6= j, we have that Ex∈[n] 1ci (x)=w(x)=cj (x) 6 η since the relative distance of C is at least 1 − s, and ci , cj are codewords. Plugging this above we get δ 2 6 2.5 1 k + s, hence k 6 1 . δ 2 −s The Inductive Argument Finally, we explain how to get Theorem 1.5 by induction on m. For that, we need the following generalization of Theorem 2.8. Theorem 2.13. Suppose that B0 , Bm−1 are tables that pass the (m − 1)-dimensional space versus point d2 test with probability at least ε > q1/10 . Then there exists a polynomial f : Fm q → Fq of total degree d, such that d10 Prm [f (x) = B0 (x)] > ε − 1/10 . x∈Fq q Proof. The argument is similar to the argument in Theorem 2.8, and we do not give the details. We remark that following the strategy therein, the bulk of the proof boils down to proving an analog of Theorem 2.1 for the (m − 1)-dimensional affine subspace vs (m − 1)-dimensional affine subspace test in Fm q , and the same analysis that we showed works. Therein, the main fact we used m = 3 for is that random two planes in F3q intersect, with high probability, on a line. In the current setting it is true that two randomly chosen (m − 1)dimensional affine subspaces in Fm q intersect, with high probability, in an affine subspace of dimension m − 2. We can now prove Theorem 1.5 by induction on m, restated below. Theorem 1.5 (Restated) . Suppose that B0 , B2 are tables that pass the plane versus point test with probad2 bility at least ε > q1/10 . Then there exists a polynomial f : Fm q → Fq of total degree d, such that Prm [f (x) = B0 (x)] > ε − m x∈Fq d10 . q 1/10 Proof. We prove by induction on m. For m = 3, the statement is true from Theorem 2.8. Assume the statement for m > 3, and prove for m + 1. Then we are working over Fm+1 . For each W ⊆ Fm+1 of q q dimension m, we may consider the plane versus point test there; let εW be the acceptance probability of it there, and note that EW [εW ] = ε. By induction hypothesis, we may find fW : W → Fq of degree d such that d10 Pr [fW (x) = B0 (x)] > εW − m 1/10 , x∈W q 11 so we may define an assignment Bm that assigns to each m dimensional subspace W ∈ Bm (Fm+1 ) the q function fW , and get that B0 , Bm pass the m-dimensional subspace versus point test with probability     d10 d10 ε − m Pr [f (x) = B (x)] > = ε − m . E W E 0 W q 1/10 q 1/10 W W x∈P ∈S2 (W ) Applying Theorem 2.13 we find a polynomial f : Fm+1 → Fq of degree at most d satisfying that q Pr x∈W ∈Sm (Fm+1 ) q 2.6 [B0 (x) = f (x)] >   d10 d10 d10 ε − m 1/10 − 1/10 = ε − (m + 1) 1/10 . q q q Proof of the List Decoding Statement, Theorem 1.6 Proof of Theorem 1.6. Let f1 , . . . , fk be all degree d functions that agree with B0 on at least δ fraction of points; by Claim 2.12, k 6 δ22 , and we next perform a randomization argument as before. Let Wi ⊆ Fm q be the set of points on which fi and B0 agree, and W = W1 ∪ . . . ∪ Wk . We claim that if we randomize the values of B0 on all x ∈ W , then with high probability the acceptance probability of the plane versus point test is at most 10δ. Indeed, with high probability after the randomization no degree d function agrees with B0 on more than 2δ fraction of points, and hence by Theorem 2.13 the plane versus point test passes with probability at most 2δ. Thus, it follows that before the randomization, except with probability 2δ, whenever the test passes, B0 agrees with at least one of the functions fj . Sample P , and let E be the event that fj |P = B2 [P ] for some j. If E fails, then fj |P and B2 [P ] agree on at most dq of the points of x ∈ P , and so B2 [P ](x) = fj (x) for some j for at most dk q fraction of points x ∈ P . Thus,   Pr B0 (x) = B2 [P ](x) ∧ Ē ∧ ∃jB0 (x) = fj (x) x∈P ∈S2 (Fm q ) 6 6 Pr  x∈P ∈S2 (Fm q ) ∃j, B0 (x) = B2 [P ](x) = fj (x) | Ē  dk . q Hence, Pr x∈P ∈S2 (Fm q )   B0 (x) = B2 [P ](x) ∧ Ē 6 which is at most 2δ + dk q > 2δ + 2d qδ 2 Pr x∈P ∈S2 (Fm q ) 6 3δ. 12 [B0 (x) = B2 [P ](x) ∧ ∀jB0 (x) 6= fj (x)] + dk , q