BLR Linearity testing

Suppose we are given a function $f:\mathbb F_2^n\to\mathbb F_2$ . We would like to know whether it is linear, meaning that it has the form $f(x)=a_1x_1+\cdots+a_nx_n$ , where the coefficients $a_i$ belong to $\mathbb F_2$ . All additions here are modulo two. There is another way to describe linearity, without referring to the coefficients: a function is linear precisely when

$\displaystyle f(x+y)=f(x)+f(y)$

for every pair $x,y\in\mathbb F_2^n$ . This is easy to see in one direction, since a linear expression preserves addition. Conversely, if the identity holds for every pair, then $f(0)=0$ , and by writing $x=x_1e_1+\cdots+x_ne_n$ in terms of the standard basis vectors, we obtain $f(x)=x_1f(e_1)+\cdots+x_nf(e_n)$ . The first description is global: it says that one choice of $n$ coefficients determines the function everywhere. The second is local: it gives a simple relation involving only three values of the function.

Now suppose the local identity holds for most pairs $(x,y)$ , but not necessarily all of them. Does it follow that the function is close to some linear function? More importantly, can we tell whether a function is close to linear by checking only a few randomly chosen values, rather than examining its entire truth table of size $2^n$ ? This is the question behind the BLR linearity test, introduced by Blum, Luby and Rubinfeld. The test is remarkably simple.

BLR linearity test: Choose $x,y\in\mathbb F_2^n$ independently and uniformly at random, query $f(x),f(y),f(x+y)$ , and accept exactly when

$f(x)+f(y)=f(x+y)$ .

If $f$ is linear, every test passes. The interesting question is what happens when $f$ is not linear. A function could violate some of these identities without being very far from linear. What we want is a quantitative relationship between the fraction of identities that fail and the fraction of values we would need to change to make the function linear. Let $\varepsilon$ be the distance from $f$ to the nearest linear function, and let $\delta$ be the probability that the BLR test rejects:

$\displaystyle \varepsilon=\min_{a\in\mathbb F_2^n}\Pr_x[f(x)\neq\langle a,x\rangle],\qquad \delta=\Pr_{x,y}[f(x)+f(y)\neq f(x+y)].$

We will prove the following bounds:

$\displaystyle\varepsilon\le\delta\le3\varepsilon.$

The second inequality is fairly easy: if the function differs from a linear function at only a few points, a random test is unlikely to encounter one of those points. The first is more interesting. It says that if a random local test almost always passes, then there really is a single linear function agreeing with $f$ on almost the entire space. We will first prove this using Fourier analysis, which gives the stronger constant. Then we will give a second proof based on decoding: using the local identities themselves to reconstruct a linear function. The two arguments explain different aspects of why the test works.

The Fourier proof

The first question is how to express the acceptance probability in a form that Fourier analysis can handle. Since $f$ takes values in ${0,1}$ , it is convenient to change to the sign representation $\displaystyle F(x)=(-1)^{f(x)}.$ Now $F(x)$ is always $1$ or $-1$ , and addition modulo two becomes multiplication of signs. In particular,

$\displaystyle f(x)+f(y)=f(x+y)\quad\Longleftrightarrow\quad F(x)F(y)F(x+y)=1.$

If the test accepts, this product is $1$ ; if it rejects, the product is $-1$ . So its expectation is the acceptance probability minus the rejection probability, or $1-2\delta$ . Equivalently,

$\displaystyle \Pr[\text{accept}]=\frac12+\frac12\mathbb E_{x,y}F(x)F(y)F(x+y).$

This is a good reason for using the sign representation. The condition originally involved addition modulo two, but we have converted it into an ordinary product of three real numbers. We now expand $F$ in the Fourier basis. For $a\in\mathbb F_2^n$ , let $\chi_a(x)=(-1)^{\langle a,x\rangle}$ be the corresponding character. Then

$\displaystyle F(x)=\sum_{a\in\mathbb F_2^n}\widehat F(a)\chi_a(x),\qquad \widehat F(a)=\mathbb E_xF(x)\chi_a(x).$

Substituting the expansion into the expectation gives

$\displaystyle \mathbb E_{x,y}F(x)F(y)F(x+y)=\sum_{a,b,c}\widehat F(a)\widehat F(b)\widehat F(c),\mathbb E_{x,y}\chi_a(x)\chi_b(y)\chi_c(x+y).$

At first this is a triple sum, but the characters make nearly every term vanish. Since characters are multiplicative with respect to addition, $\chi_c(x+y)=\chi_c(x)\chi_c(y)$ . Thus the expectation in the sum becomes

$\displaystyle \mathbb E_x\chi_{a+c}(x)\cdot\mathbb E_y\chi_{b+c}(y).$

A nontrivial character has average zero. Consequently, this product vanishes unless $a+c=0$ and $b+c=0$ , which in characteristic two means $a=b=c$ . Only the terms with three identical frequencies survive. We obtain the central identity of the proof:

$\displaystyle \boxed{Pr[\text{accept}]=\frac12\left(1+\sum_{a\in\mathbb F_2^n}\widehat F(a)^3\right).}$

This cubic expression is not accidental. The BLR test examines three points satisfying one additive relation. When we expand their Fourier characters, orthogonality forces all three frequencies to be equal. There is a useful parallel with the Fourier proof of Roth’s theorem over $\mathbb F_3^n$ . There too, a three-variable configuration gives a sum of cubes of Fourier coefficients. The underlying mechanism is the same: an additive relation among the sampled points becomes a relation among frequencies, and character orthogonality removes almost the entire expansion.

We have expressed the acceptance probability using Fourier coefficients. But our theorem concerns the distance from $f$ to a linear function. How are these related? Fix $a\in\mathbb F_2^n$ and consider the linear function $L_a(x)=\langle a,x\rangle$ . By definition,

$\displaystyle \widehat F(a)=\mathbb E_x(-1)^{f(x)+L_a(x)}.$

The expression inside the expectation is $1$ when $f(x)=L_a(x)$ , and $-1$ when they disagree. Therefore

$\displaystyle \boxed{\widehat F(a)=1-2\Pr_x[f(x)\neq L_a(x)].}$

So the Fourier coefficient at frequency $a$ measures how well $f$ agrees with the linear function $L_a$ . For example, if they agree everywhere, the coefficient is $1$ . If they disagree at ten percent of the points, the coefficient is $0.8$ . If they agree at exactly half the points, it is zero. A negative coefficient means they disagree more often than they agree. Since $\varepsilon$ is the smallest possible disagreement over all linear functions, we have

$\displaystyle \max_a\widehat F(a)=1-2\varepsilon.$

This is the main reason Fourier analysis is so well suited to the problem. The linear functions we are trying to find are exactly the functions appearing in the Fourier basis. Finding a linear function close to $f$ is the same as finding a large positive Fourier coefficient of $F$ . We now have everything we need. Parseval’s identity gives

$\displaystyle \sum_a\widehat F(a)^2=\mathbb E_xF(x)^2=1,$

since $F(x)$ is always a sign. Let $M=\max_a\widehat F(a)=1-2\varepsilon$ . Every Fourier coefficient is real and at most $M$ . Multiplying this inequality by the nonnegative quantity $\widehat F(a)^2$ , we obtain $\widehat F(a)^3\le M\widehat F(a)^2$ . Summing over all frequencies,

$\displaystyle \sum_a\widehat F(a)^3\le M\sum_a\widehat F(a)^2=1-2\varepsilon.$

Substituting into the expression for the acceptance probability,

$\displaystyle \Pr[\text{accept}]\le\frac12(1+1-2\varepsilon)=1-\varepsilon.$

Hence

$\displaystyle \Pr[\text{reject}]\ge\varepsilon.$

This proves the difficult direction of the theorem. It is worth noticing how little we needed once the Fourier identity was established. Parseval tells us that the Fourier coefficients have total squared mass one. The cubic sum cannot exceed the largest coefficient times that squared mass. But the largest coefficient tells us exactly how close the function is to a linear function. We can also read the argument backward. If the test accepts with probability $1-\delta$ , then the cubic Fourier sum equals $1-2\delta$ . Since this sum cannot exceed the largest Fourier coefficient, some frequency satisfies $\widehat F(a)\ge1-2\delta$ . The corresponding linear function $L_a$ agrees with $f$ on at least a $1-\delta$ fraction of the inputs. Thus a large acceptance probability is not merely evidence that the function is approximately linear. It guarantees the existence of a particular linear function that explains most of its values.

The other direction is much simpler and does not need Fourier analysis. Let $L$ be a closest linear function, and suppose $f$ differs from $L$ on an $\varepsilon$ fraction of the inputs. Call these inputs errors. The BLR test queries the three points $x,y,x+y$ . If $f$ agrees with $L$ at all three points, the test certainly accepts, because $L$ is linear. Thus a rejection is possible only if at least one of the three queried values is an error. Each of $x,y,x+y$ is uniformly distributed in $\mathbb F_2^n$ , so each is an error with probability $\varepsilon$ . By the union bound,

$\displaystyle \Pr[\text{reject}]\le3\varepsilon.$

Combining this with the Fourier argument gives the desired theorem:

$\displaystyle \varepsilon\le\delta\le3\varepsilon.$

The upper bound shows that the test does not reject too often when the function is close to linear. The lower bound shows that it cannot accept too often when the function is far from every linear function. The two directions are quite different. The upper bound follows by comparing $f$ with a known nearby linear function. The lower bound is an inverse statement: from the fact that many local identities hold, we must prove that some nearby linear function exists.

It is also useful to consider what different acceptance probabilities tell us. If the BLR test accepts almost always, then the function must be close to linear: for example, 99% acceptance means that some linear function agrees with $f$ on at least 99% of the inputs. Interestingly, the opposite extreme also tells us something. If the test accepts only 1% of the time, then $f$ must be within 1% of a function of the form $L(x)+1$ , where $L$ is linear. Indeed, replacing $f$ by $f+1$ interchanges acceptance and rejection. What happens around 50% acceptance? Here we cannot conclude that the function is close to either type of function. A random Boolean function typically passes about half the tests, but even simple nonlinear functions, such as quadratic polynomials, can have acceptance probabilities very close to 50%. In fact, if the acceptance probability is exactly 50%, the function must be at least $1/6$ away from every linear function and every function of the form $L+1$ , although it may be much farther away. Thus the test is most informative near the two extremes: acceptance near 100% detects linearity, acceptance near 0% detects linearity with the constant term flipped, and acceptance near 50% gives much less information about the function.

The estimate $\delta\le3\varepsilon$ comes from a union bound, but we can understand the rejection probability more precisely. Write $f=L+e$ , where $L$ is a closest linear function and $e:\mathbb F_2^n\to \{0,1\}$ is the error indicator. Thus $e(x)=1$ exactly when $f(x)\neq L(x)$ , and $\Pr[e(x)=1]=\varepsilon$ . Since $L$ is linear, its contribution cancels in the BLR condition. The test rejects exactly when

$\displaystyle e(x)+e(y)+e(x+y)=1\pmod2.$

This gives a slightly surprising observation. The test does not reject whenever it sees an error. It rejects when it sees an odd number of errors among its three queried values. In particular, two errors can cancel each other. This is why the union bound is not an exact formula. There is a simple way to calculate the rejection probability from these possibilities. For bits $u,v,w\in \{0,1\}$ , the indicator that $u+v+w$ is odd equals $u+v+w-2(uv+uw+vw)+4uvw$ . Apply this with $u=e(x)$ , $v=e(y)$ , and $w=e(x+y)$ . Each individual error has probability $\varepsilon$ . More importantly, every pair among $x,y,x+y$ is independent and uniformly distributed, even though all three points are not independent. For instance, the map $(x,y)\mapsto(x,x+y)$ is a bijection of the product space. Therefore each pair of error indicators has expectation $\varepsilon^2$ . Let $\tau=\Pr[e(x)=e(y)=e(x+y)=1]$ . Taking expectations gives the exact formula

$\displaystyle \delta=3\varepsilon-6\varepsilon^2+4\tau.$

The quantity $\tau$ measures how often all three points of a randomly chosen additive triple lie in the error set. It depends on the additive structure of that set, not merely on its size. Since $0\le\tau\le\varepsilon^2$ , we obtain the more precise bounds

$\displaystyle 3\varepsilon-6\varepsilon^2\le\delta\le3\varepsilon-2\varepsilon^2.$

Together with the Fourier lower bound, this tells us

$\displaystyle \max \{\varepsilon,,3\varepsilon-6\varepsilon^2 \}\le\delta\le3\varepsilon-2\varepsilon^2.$

For small $\varepsilon$ , the two quadratic bounds are very close. In fact, $\delta=3\varepsilon+O(\varepsilon^2)$ . So when the function differs from a linear function on only a tiny fraction of inputs, the test rejects with probability approximately three times that fraction. This makes sense. For a very small error set, a random test usually encounters no errors. The main way it can fail is to encounter exactly one, and there are three queried positions at which that error might occur. Events involving two or three errors have probability of order $\varepsilon^2$ .

The refined identity also shows why the exact rejection probability cannot depend only on $\varepsilon$ . Two error sets of the same size may have different additive structure and therefore different values of $\tau$ . For example, let the error set be a subspace $H\le\mathbb F_2^n$ of density $\varepsilon$ , and take $f=1_H$ . For $\varepsilon\le1/2$ , the zero function is a closest linear function. If $x,y\in H$ , then $x+y\in H$ , so $\tau=\varepsilon^2$ . The rejection probability is therefore $3\varepsilon-2\varepsilon^2$ . Now take the error set to be a nonzero coset $b+H$ of a subspace of codimension at least two. Again the zero function is a closest linear function, with distance $\varepsilon=|H|/2^n\le1/4$ . But if $x,y\in b+H$ , then $x+y\in H$ , not in $b+H$ . Thus $\tau=0$ , giving $\delta=3\varepsilon-6\varepsilon^2$ . The two functions have the same distance to linearity, but their error sets behave differently under addition. These examples attain the two quadratic bounds for such densities.

Consider $f(x_1,x_2)=x_1x_2$ on $\mathbb F_2^2$ . The function is zero at three of the four inputs and equals one at $(1,1)$ . It has distance $\varepsilon=1/4$ from the zero linear function, and no linear function agrees with it at all four points. Its sign function $F=(-1)^f$ has four Fourier coefficients: three equal to $1/2$ and one equal to $-1/2$ . Therefore

$\displaystyle \sum_a\widehat F(a)^3=\frac38-\frac18=\frac14,$

so the test rejects with probability

$\displaystyle \delta=\frac12\left(1-\frac14\right)=\frac38.$

Thus a function at distance $1/4$ from linearity is rejected with probability $3/8$ . This example is worth remembering because it is the simplest quadratic Boolean function. The BLR test was designed to distinguish linear functions from nonlinear ones, and the first nonlinear polynomial already gives a concrete instance of its behaviour.

Another Proof – Self Correction

The Fourier proof gives the stronger quantitative result, but it does not immediately tell us how to recover a nearby linear function from queries to $f$ . There is another argument that does exactly this. Suppose first that $f$ is close to some linear function $L$ . We want to recover $L(x)$ at a particular point $x$ , possibly even when $f(x)$ itself is wrong. The linearity identity suggests a way to do this:

$\displaystyle L(x)=L(x+y)+L(y).$

The important thing is that this holds for every $y$ . We can therefore choose a random $y$ and use the two values $f(x+y),f(y)$ to guess $L(x)$ . Define the vote

$\displaystyle V_x(y)=f(x+y)+f(y).$

If $f=L$ , every vote equals $L(x)$ . If $f$ differs from $L$ on an $\varepsilon$ fraction of the inputs, the vote can be incorrect only if at least one of $f(x+y),f(y)$ is incorrect. By the union bound,

$\displaystyle \Pr_y[V_x(y)=L(x)]\ge1-2\varepsilon.$

Notice that this holds for every fixed $x$ . The point $x$ itself need not be good. We have replaced the potentially incorrect value $f(x)$ by two randomly chosen values whose sum is supposed to equal the correct answer. If $\varepsilon<1/4$ , the right side is greater than one-half. Thus a majority of the votes agree with $L(x)$ , and repeated random votes can recover its value with high probability. This is called local self-correction. We do not have to reconstruct the entire truth table of $L$ before computing its value at one point. We use the linearity identity to move the query to random locations where the function is likely to be correct. But this argument assumed that a nearby linear function already exists. Can we go in the opposite direction? If the BLR test rarely rejects, can we define a function from these majority votes and prove that it is linear? That is the decoding version of the soundness proof.

Let $\delta$ be the rejection probability of the BLR test. For every $x$ , define $g(x)$ to be the majority value of the votes $V_x(y)=f(x+y)+f(y)$ , as $y$ ranges uniformly over the space. If there is a tie, choose either value. We would like to prove that these majority values form a linear function. The difficulty is that the test rejects with probability $\delta$ only on average over $x,y$ . At a particular point $x$ , we do not yet know that most votes agree with $f(x)$ . Some values of $f(x)$ may be badly corrupted. What we can prove is that, for each fixed $x$ , most votes $V_x(y)$ agree with one another. The reason comes from comparing two votes. Take independent random $y,z$ . Their votes are $V_x(y)=f(x+y)+f(y)$ and $V_x(z)=f(x+z)+f(z)$ . Put $t=y+z$ . Since we are working over $\mathbb F_2$ , we have $z=y+t$ , and hence

$\displaystyle V_x(y)+V_x(z)=\bigl(f(y)+f(t)+f(y+t)\bigr)+\bigl(f(x+y)+f(t)+f(x+y+t)\bigr).$

Each parenthesis is the expression tested by BLR for a pair of inputs. The first is the test on $(y,t)$ ; the second is the test on $(x+y,t)$ . Both pairs are uniformly distributed when $y,z$ are uniform and independent. Therefore, if the two votes disagree, at least one of these two BLR checks must fail. By the union bound,

$\displaystyle \Pr_{y,z}[V_x(y)\neq V_x(z)]\le2\delta.$

The key point is that this estimate holds for every fixed $x$ . We have used the overlapping additive relations to turn an average statement about the test into a uniform statement about the consistency of the votes. Now suppose a binary random variable takes its minority value with probability $p\le1/2$ . Two independent samples disagree with probability $2p(1-p)$ , which is at least $p$ . Thus the probability that a vote disagrees with its majority value is at most the probability that two independent votes disagree. Applying this to $V_x(y)$ , we obtain

$\displaystyle \Pr_y[V_x(y)\neq g(x)]\le2\delta\qquad\text{for every }x.$

So the majority vote is reliable at every point, even though the original function may be unreliable at some points. We now want to prove $g(x)+g(z)=g(x+z)$ . Fix any $x,z$ and choose a random $y$ . Consider the three identities

$\displaystyle g(x)=f(x+y)+f(y), g(z)=f(x+z+y)+f(x+y), g(x+z)=f(x+z+y)+f(y).$

Each is a statement that one vote agrees with the majority value at its corresponding point. By the preceding estimate, each fails with probability at most $2\delta$ . By the union bound, all three identities hold simultaneously with probability at least $1-6\delta$ . In particular, if $\delta<1/6$ , there must exist some $y$ for which all three are true. For this $y$ , add the first two identities. The two occurrences of $f(x+y)$ cancel modulo two, leaving

$\displaystyle g(x)+g(z)=f(x+z+y)+f(y)=g(x+z).$

Since $x,z$ were arbitrary, $g$ is linear. This is the central step in the decoding proof. We did not begin with a linear function and check that it explains the data. We defined $g$ from the data by taking majority votes, and then proved that these votes necessarily fit together into a linear function. Why does this work? Because the three expressions used to vote for $g(x),g(z),g(x+z)$ are not unrelated. They share values of $f$ , and when the three votes are correct, their algebraic relation forces the desired linearity identity.

It remains to show that $g$ agrees with $f$ on most inputs. Recall that $V_x(y)=f(x+y)+f(y)$ . The BLR test rejects on the pair $(x,y)$ exactly when $V_x(y)\neq f(x)$ . Thus

$\displaystyle \delta=\Pr_{x,y}[V_x(y)\neq f(x)].$

If $g(x)\neq f(x)$ , then $f(x)$ is not the majority value of the votes $V_x(y)$ . Consequently, at least half the votes disagree with $f(x)$ . Averaging over $x$ gives

$\displaystyle \delta\ge\frac12\Pr_x[g(x)\neq f(x)].$

Therefore

$\displaystyle \Pr_x[g(x)\neq f(x)]\le2\delta.$

We have proved that if the BLR test rejects with probability less than $1/6$ , then the majority-vote function $g$ is linear and differs from $f$ on at most a $2\delta$ fraction of inputs. This is weaker than the Fourier theorem, which guarantees distance at most $\delta$ without assuming $\delta<1/6$ . But the decoding proof gives something the Fourier proof does not directly provide: a concrete way of defining the corrected function at any point, using values of $f$ at randomly chosen nearby pairs. The condition $\delta<1/6$ appears because we needed three majority-vote identities to hold simultaneously, and each had failure probability at most $2\delta$ . It is a sufficient condition for this particular argument, not a threshold at which the BLR test suddenly stops working. The sharper Fourier guarantee holds for every function.

Bounds

We have proved $\varepsilon\le\delta\le3\varepsilon$ . Could the constants be improved? For very small $\varepsilon$ , the exact counting formula from above shows that $\delta=3\varepsilon+O(\varepsilon^2)$ . So the factor three in a universal linear upper bound cannot be replaced by a smaller constant. A function that differs from a linear one on a very small number of points is rejected approximately three times as often as its error rate. The factor one in the lower bound is also the best possible universal linear constant, although this is easiest to see for functions whose distance to linearity is close to one-half. Consider the quadratic function on $2m$ variables

$\displaystyle f(x)=x_1x_2+x_3x_4+\cdots+x_{2m-1}x_{2m}.$

For a single pair of variables, the sign function $(-1)^{x_1x_2}$ has four Fourier coefficients, each of absolute value $1/2$ . For $m$ independent pairs, the Fourier coefficients are products of these coefficients, so all have absolute value $2^{-m}$ , and some are positive. It follows that the distance to the closest linear function is

$\displaystyle \varepsilon=\frac{1-2^{-m}}2.$

We can also calculate the rejection probability directly. The BLR error expression for each pair is $x_{2j-1}y_{2j}+x_{2j}y_{2j-1}$ . Its sign has expectation $1/4$ , and the contributions from the different pairs are independent. Thus the full acceptance-minus-rejection bias is $4^{-m}$ , giving

$\displaystyle \delta=\frac{1-4^{-m}}2.$

Consequently,

$\displaystyle \frac{\delta}{\varepsilon}=1+2^{-m}.$

As $m\to\infty$ , this ratio tends to one. So even though the rejection probability is almost three times the distance when the distance is very small, it can be barely larger than the distance when the function is far from linear. These examples explain why the two constants in the theorem are both natural. Near a linear function, an isolated error can be detected through any of the three queried positions, producing the factor three. Far from linearity, the Fourier spectrum can be spread over many frequencies, and the rejection probability can be close to the distance itself. The exact relationship between distance and rejection probability is therefore more interesting than a single linear inequality. It depends not only on how many errors the function has relative to its closest linear approximation, but also on how those errors are arranged under addition. This was studied in greater detail by Bellare, Coppersmith, Håstad, Kiwi and Sudan in their 1996 work on linearity testing in characteristic two.

It is useful to compare the two proofs, because they suggest different ways to think about the problem. In the Fourier proof, we first change the function from bits to signs. That makes the local equation multiplicative. Expanding the product $F(x)F(y)F(x+y)$ in characters is then natural, because characters themselves preserve the addition operation. Orthogonality leaves a sum of cubes. The rest follows from a simple inequality: a cubic Fourier sum is bounded by the largest Fourier coefficient times the total squared Fourier mass. The decisive observation is that the largest positive Fourier coefficient is not some unrelated analytic quantity. It measures the agreement with the best linear function. Thus the Fourier representation is exactly adapted to the property we are testing.

The decoding proof begins from a different question. If the function is supposed to be linear, how would we repair a value that might be incorrect? The equation $f(x)=f(x+y)+f(y)$ suggests asking random pairs of points to vote for the value at $x$ . The problem is then to show that different votes are consistent. That consistency comes from the overlapping additive relations. Two votes for the same point can disagree only if at least one of two BLR checks fails. This gives a reliable majority value for every point. To prove that the majority values are linear, we use three carefully chosen votes whose intermediate function values cancel. So the same identities that define the test also provide a way to reconstruct a global linear function. In this sense, the BLR test is doing more than checking a collection of unrelated equations. The local constraints overlap so heavily that their values cannot behave independently. If almost all constraints hold, the values at different points are forced to fit together into one global linear rule.

There is also a coding-theoretic interpretation. The truth table of each linear function is a codeword of the Hadamard code. These codewords have length $2^n$ , but the BLR test examines only three locations. The Fourier theorem says that the probability of rejecting a truth table is at least its relative distance from the closest codeword. The decoding argument shows how, when the corruption is sufficiently small, individual codeword symbols can be recovered from random pairs of received symbols. This is why linearity testing is useful in probabilistically checkable proofs. A verifier may be given an enormous table claiming to describe a linear function. It cannot afford to inspect the entire table, but it can sample a few local constraints. A truly linear table always passes, while a table far from every linear function is caught with probability proportional to its distance.

The main result can be stated quite simply. If the BLR test rejects with probability $\delta$ , then there is some linear function differing from $f$ on at most a $\delta$ fraction of inputs. Conversely, if the nearest linear function differs from $f$ on an $\varepsilon$ fraction, then the rejection probability is at most $3\varepsilon$ , and in fact is approximately $3\varepsilon$ when $\varepsilon$ is small. The important point is the passage from local to global: knowing that most additive identities hold is enough to guarantee that one linear function explains most of the values. Fourier analysis proves this through the concentration of a cubic sum, while majority decoding proves it by showing that the local equations give consistent ways of reconstructing the same function.

Share this:

Related

Leave a Reply Cancel reply