<?xml-model href='http://www.tei-c.org/release/xml/tei/custom/schema/relaxng/tei_all.rng' schematypens='http://relaxng.org/ns/structure/1.0'?><TEI xmlns="http://www.tei-c.org/ns/1.0">
	<teiHeader>
		<fileDesc>
			<titleStmt><title level='a'>On Optimal Testing of Linearity</title></titleStmt>
			<publicationStmt>
				<publisher>SIAM Symposium on Simplicity in Algorithms</publisher>
				<date>01/01/2025</date>
			</publicationStmt>
			<sourceDesc>
				<bibl> 
					<idno type="par_id">10636647</idno>
					<idno type="doi"></idno>
					
					<author>Vipul Arora</author><author>Esty Kelman</author><author>Uri Meir</author>
				</bibl>
			</sourceDesc>
		</fileDesc>
		<profileDesc>
			<abstract><ab><![CDATA[Linearity testing has been a focal problem in property testing of functions. We combine different known techniques and observations about Linearity testing in order to resolve two recent versions of this task.First, we focus on the online-manipulation-resilient model introduced by Kalemaj, Raskhodnikova and Varma (Theory of Computing 2023). In this model, up to t data entries are adversarially manipulated after each query is answered. Ben-Eliezer, Kelman, Meir, and Raskhodnikova (ITCS 2024) showed an asymptotically optimal Linearity tester that is resilient to t manipulations per query, but fails if t is too large. We simplify their analysis for the regime of small t, and for larger values of t we instead use sample-based testers, as defined by Goldreich and Ron (ACM Transactions on Computation Theory 2016). A key observation is that sample-based testing is resilient to online manipulations but still achieves optimal query complexity for Linearity when t is large. We complement our result by showing that when t is very large any reasonable property, and in particular Linearity, cannot be tested at all.Second, we consider Linearity over the reals with proximity parameter ε. Fleming and Yoshida (ITCS 2020) gave a tester using O (1/ε · log (1/ε)) queries. We simplify their algorithms and modify the analysis accordingly, showing an optimal tester that only uses O (1/ε) queries. This modification works for the low-degree testers presented in Arora, Bhattacharyya, Fleming, Kelman, and Yoshida (SODA 2023) as well, resulting in optimal testers for degree-d polynomials, for any constant d.]]></ab></abstract>
		</profileDesc>
	</teiHeader>
	<text><body xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xlink="http://www.w3.org/1999/xlink">
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1">Introduction</head><p>In the field of property testing <ref type="bibr">[RS96,</ref><ref type="bibr">GGR98]</ref>, a randomized algorithm is given oracle access to a large object, and a promise that the object either has some property (YES instances), or is "far" from having it (NO instances), under some notion of distance. The goal of the algorithm is to distinguish between the two cases with success probability at least 2/3, where the complexity is measured by the number of oracle calls made (this is well justified, as the running time is typically polynomial in the query complexity).</p><p>Linearity testing. In this manuscript, we focus on testing functions over a field F (in particular F = F 2 and F = R). That is, the tester is allowed oracle access to some function f : F n &#8594; F and distinguishes functions with a desired property from ones that are far from any function satisfying the property. The most studied property of functions is Linearity, for which a tester was first given in <ref type="bibr">[BLR93]</ref>, perhaps the earliest instance of a property tester in the literature. The test, dubbed "the 3 points test" simply draws two random points x, y &#8712; F n and accepts only if f (x) + f (y) = f (x &#8853; y), where + denotes addition over F, and &#8853; denotes point-wise addition. By definition, if f is linear, this equality must hold for any pair x, y. It was shown in various settings that if f is &#949;-far from linear, there is an inequality for at least an &#8486;(&#949;)-fraction of the pairs x, y. [BLR93, BCH + 96, FY20]. Thus, repeating the process &#952;(1/&#949;) times defines a tester for linearity with the same query complexity. We note this tester satisfies the additional requirement of never rejecting a linear function, making it a 1-sided error tester for linearity.</p><p>It is well known that &#8486;(1/&#949;) oracle calls are necessary to test linearity (and most reasonable properties <ref type="bibr">[Fis24]</ref>), proving the 3 points test of <ref type="bibr">[BLR93]</ref> is optimal in terms of query complexity.</p><p>1.1 Online erasures over the Boolean field Linearity was studied extensively over the Boolean field F 2 [BLR93,BS94,FGL + 96,BCH + 96,BGS98,Tre98,ST98,ST00,HW03,BSVW03,Sam07,ST09,SW06,KLX10,KRV23] and the survey in <ref type="bibr">[RR16]</ref>. Before we present the erasure model, we first review the ideas from previous works that are used in our result.</p><p>k-point test. Recently, in the context of online erasures over F = F 2 (which we describe soon), the k-points test was proposed by <ref type="bibr">[KRV23]</ref>. In this test, which generalizes the 3-point test, the algorithm chooses points x 1 , . . . , x k-1 at random, and accepts only if i&#8712;[k-1] f (x i ) = f &#8853; i&#8712;[k-1] x i . It was later shown by <ref type="bibr">[BKMR24]</ref> that repeating the k-points test &#920;(1/(k&#949;)) times produces an optimal Linearity tester for any k = O(1/&#949;).</p><p>sample-based testers. Linearity over F 2 was also considered in <ref type="bibr">[GR16]</ref> using a weaker oracle access, where the tester cannot retrieve f (x) for a value x of its choice, but instead each oracle call outputs a pair (x, f (x)) with a uniformly random choice of x &#8712; R F n 2 . A tester using such oracle access is called a sample-based tester <ref type="bibr">[GGR98]</ref>. It was shown in <ref type="bibr">[GR16]</ref> that &#920; (n + 1/&#949;) samples are sufficient and necessary to test Linearity. The gist is that a linear function is determined by its value on a basis B of the entire space F n 2 . After &#920;(n) samples, one can extrapolate some linear function g, and use the remaining 1/&#949; samples to compare f and g. A formal argument for this setting, without online erasures, appears in Section 2.2.</p><p>The online erasure model was recently introduced by <ref type="bibr">[KRV23]</ref>. In this model, after each query is answered, t data points go through manipulations. These can be either (1) erasures, where an entry f (x) is replaced with &#8869;; or (2) corruptions, where an entry f (x) can be changed to any value in the range of f .</p><p>In particular, they study Linearity testing over F 2 . First, they note the 3-points-test is fragile in the presence of an adversary: a tester that insists on querying a triplet of the form (x, y, x + y) must make &#8486; (t) queries, as fewer queries allow the adversary to erase all (new) pairs that were created at each step. To overcome this, they devise the k-points test, which creates more combinations, and eventually leads to a tester with query complexity O(log t/&#949;). It was then pointed out in <ref type="bibr">[BKMR24]</ref> that the k-point test not only preserves the probability of spotting a violation, but actually increases it by a factor of &#8776; k -this is enough to reach query complexity of log t + 1/&#949;, which is optimal. Indeed, a lower bound of &#8486;(log t) was shown for this model by <ref type="bibr">[KRV23]</ref>, and an &#8486;(1/&#949;) holds even without erasures. Another recent work by Minzer and Zheng <ref type="bibr">[MZ24]</ref> showed a striking O( log &#920;(d) (t)) tester for any degree-d and any finite field. For the case of Linearity (d = 1), however, their result is suboptimal , achieving a query complexity of O log 6 (t/&#949;)/&#949; .</p><p>How many erasures can the tester handle? All the above testers share a similar limitation: they all require t &#8804; 2 n/c for some c &#8805; 2 (See Table <ref type="table">1</ref> for the precise values). It is natural to ask what is the highest value of t for which Linearity is still testable. Clearly, t = 2 n is too much, but how close can we get?</p><p>In Section 2 we fully resolve this question. Our observation, roughly speaking, is that all previous testers include some queries that are "too predictable", making them susceptible to adversarial manipulations. However, this only occurs when the adversary has very large manipulation budget t = 2 &#8486;(n) , in which case we can simply apply the sample-based tester instead, killing two birds at once. First, sample-based testers almost automatically overcome online manipulations. Second, the seemingly high sample complexity of the tester is actually optimal as in this regime we have &#920;(log(t) + 1/&#949;) = &#920;(n + 1/&#949;). Formally, we have the following.</p><p>Theorem 1.1. (Doubly-efficient tester) There exists a constant c &gt; 0 such that for all n &#8712; N, &#949; &#8712; (0, 1/2], and t satisfying t &#8804; c min &#949; 2 , 1/n 2 &#8226; 2 n , there exists an &#949;-tester for linearity of functions f : {0, 1} n &#8594; {0, 1} that works in the presence of a t-online erasure (or corruption) adversary and makes O (max {1/&#949;, log t}) queries. In the case of erasure adversary, the tester has 1-sided error.</p><p>Our tester can also overcome the stronger budget-managing adversary, which can "bank" their manipulation privilege and use it only when necessary. See <ref type="bibr">[BKMR24]</ref> for more details.</p><p>Finally, we show our tester is optimal in both term of query complexity and the amount of manipulations it can handle, which makes it doubly-optimal. For even a slightly larger value of t, we show that Linearity is no longer testable in the model. For any n, t, &#949; where Linearity is testable, the tester has optimal query complexity.</p><p>Theorem 1.2. &#949;-testing linearity in the online erasure model is impossible whenever for any &#949; &#8712; (0, 1/2) provided that t &#8805; 20&#949; 2 2 n .</p><p>1.2 Optimal Linearity tester over the Reals Over the reals, there is a distinction between Result Query Complexity Range of Erasures Reference Lower bound &#8486;(log(t) + 1/&#949;) any t</p><p>Table <ref type="table">1</ref>: A comparison of all known testers for linearity in the online erasure model. For the sake of clarity, in the column for the range of erasures, we hide factors of poly(n/&#949;).</p><p>&#8226; linearity: f (x) &#8801; n i=1 c i x i , for some {c i &#8712; R, i &#8712; {1, . . . , n}}, and</p><p>In fact, the 3 point BLR test checks for additivity, and this alone does not guarantee linearity due to some pathological examples that are additive, but not linear <ref type="bibr">[Ham05]</ref>. We therefore assume the function f is continuous, as was done in previous works, and focus on testing additivity instead. The best known result [FY20, Theorem 1, Algorithms 3, 2] for distribution-free additivity tester uses O( 1 &#949; log( 1 &#949; )) queries. Their algorithm uses the 'self-correct and test' approach. First, they test if f violates additivity over a sufficiently large (&#920;( 1 &#949; )) random set of points. They then define the self-correction function g : R n &#8594; R of f as follows:</p><p>where</p><p>, and</p><p>Here, every p &#8712; R n is radially contracted to the point p/&#954; p &#8712; B(0, 1/50), and g x (p) is the self-correction vote contributed by the direction x &#8712; R n , weighted as per the distribution N (0, I). The majority of these votes decides the value of g(p). If no violations of additivity are found, then the g is proven to be a well defined, additive function. Next, they build an (O(log 1 &#949; ))-query access for g, and using it, they estimate the distance between f and g. This allows them to build a distribution-free tester, which is desirable as we may have no prior information about the underlying distribution. This thus avoids making any unrealizable assumptions about it.</p><p>For a measurable function f : R n &#8594; R, a distance parameter &#949; &gt; 0, an unknown but samplable distribution D supported over R n , and a property P, f is &#949;-far from P with respect to D if</p><p>An algorithm is a distribution-free tester for P, if given query access to f , sample access to D and N (0, I), and &#949; &gt; 0, it accepts all f &#8712; P with probability at least 2/3, and rejects all f such that &#948; D (f, P) &gt; &#949;, with probability at least 2/3.</p><p>To shave off the log 1 &#949; factor, we only need to modify the distance estimator part of the tester.</p><p>Theorem 1.3. There exists a distribution-free, one-sided error O(1/&#949;)-query additivity tester over the reals.</p><p>We replace the O(log 1 &#949; )-query access for g at any point p &#8712; R n with g x (p), where x &#8764; N (0, I) is a random direction. Analysis-wise, the proof for completeness remains the same. For soundness, using the approach of [HK04], we argue that g(p) agrees with at least 9/10 of the g x (p)'s (not just at least 1/2 of them). Consequently, evaluating g q (p) in a random direction x &#8764; N (0, I), i.e. g x (p) is sufficient to successfully query g(p).</p><p>Low-degree testing over the reals. We observe that the same modification applies to the Distribution-free Low degree testers (Algorithms 2, 4, and 6), as well as the Approximate Additivity (Linearity) Tester (Algorithm 8) of [ABF + 23], shaving off the log 1 &#949; factor from their query complexity (O( 1 &#949; log 1 &#949; ) for constant d case), thus giving optimal query complexity for constant d as well. We state the results here. The proofs of these improvements are very similar to the proof of Theorem 1.3, and will appear in the full version of this paper.</p><p>Theorem 1.4. Let d &#8712; N, and for L &gt; 0, suppose f : R n &#8594; R is a function that is bounded in the ball B(0, L). Given &#949; &gt; 0, query access to f , and sampling access to an unknown distribution D, there exists a one-sided error, distribution-free, O(d 5 + d 2 /&#949;)-query tester for testing whether f is a degree-d polynomial, or is &#949;-far from degree-d polynomials over D.</p><p>, query access to f , and sampling access to D, there is a one-sided error, O(d 5 + d 2 /&#949;)query tester which distinguishes between the cases when:</p><p>&#8226; f is pointwise &#945;-close to some degree-d polynomial, say h, i.e., |f (x) -h(x)| &#8804; &#945;, for every x &#8712; R n , and,</p><p>&#8226; for every degree-d polynomial h :</p><p>Given &#949; &gt; 0, query access to a function f : R n &#8594; R, and sample access to an unknown (&#949;/4, R)-concentrated distribution D supported on L, there is a one-sided error, O(d 5 + d 2 /&#949;)-query tester for testing whether f is a degree-d polynomial, or is &#949;-far from every degree-d polynomials over D. The tester queries f on points in L &#8242; .</p><p>Theorem 1.7. Let &#945;, &#949; &gt; 0 and D be an unknown (R, &#949;/4)-concentrated distribution. There exists a one-sided error, O(1/&#949;)-query tester for distinguishing between the case when f is pointwise &#945;-close to some additive function and the case when, for every additive function h,</p><p>1.3 Notation We use [n] for the set {1, 2, . . . , n} and log to denote logarithms with base 2. We use bold face, e.g. p, q, etc., to denote vectors/points over the reals.</p><p>Organization. Section 2 is devoted to the online model, wherein we provide preliminaries for online testing, as well as prove Theorem 1.1, and Theorem 1.2. Next, in Section 3, we prove Theorem 1.3. The proofs of Theorem 1.4, Theorem 1.5, Theorem 1.6, and Theorem 1.7, being similar to the proof of Theorem 1.3, will appear in the full version of this paper.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2">Testing over F with online manipulations</head><p>We start by introducing the model. The online manipulation-resilient testing model was introduced first by Kalemaj et al. <ref type="bibr">[KRV23]</ref> and formally defined by Ben-Eliezer et al. <ref type="bibr">[BKMR24]</ref>. We follow the definitions of the latter, as specified below.</p><p>The input is accessed via a sequence {O i } i&#8712;N of oracles, where O i is used to answer the i-th query. The oracle O 1 gives access to the original input (e.g., when the input is a function f , we have O 1 &#8801; f ), and subsequent oracles are objects of the same type as the input (e.g., functions with the same domain and range). Each such oracle is obtained by the adversary by modifying the previous oracle to include a growing number of erasures/corruptions as i increases. We use Dist(O, O &#8242; ) for the Hamming distance between the two oracles (i.e., the number of queries for which they give different answers). We let t &#8712; N denote the number of erasures (or corruptions) per query.</p><p>Definition 2.1. (Fixed-rate and budget-managing adversaries) Fix a parameter t &gt; 0. A sequence 1 of oracles O = {O i } i&#8712;N is induced by a t-online fixed-rate adversary if O 1 is equal to the input and, for all i &#8712; N,</p><p>A sequence of oracles O = {O i } i&#8712;N is induced by a t-online budget-managing adversary if O 1 is equal to the input and, for all i &#8712; N,</p><p>1 Our algorithms only access a finite subsequence of this sequence.</p><p>Finally, we consider two types of manipulations to the input: erasures and corruptions.</p><p>Definition 2.2. (Erasure and corruption adversaries) Let &#8869; represent the erasure symbol. A sequence of oracles O = {O i } i&#8712;N is induced by an erasure adversary if for all i &#8712; N and data points x,</p><p>In contrast, a corruption adversary can change answers to anything in the range, i.e., O i can be any valid input for the computational task at hand.</p><p>A property P denotes a set of objects (typically, a set of functions). Intuitively, it represents the set of positive instances for the testing problem. The (relative Hamming) distance between a function f and a property P, denoted dist(f, P), is the smallest fraction of function values of f that must be changed to obtain a function in P. Given a proximity parameter &#949; &#8712; (0, 1), we say that f is &#949;-far from P if dist(f, P) &#8805; &#949;. An online tester is given a proximity parameter &#949; and the rate of erasures (or corruptions) t.</p><p>Definition 2.3. (Online &#949;-tester) Fix &#949; &#8712; (0, 1). An online &#949;-tester T for a property P that works in the presence of a specified adversary (e.g., t-online erasure budget-managing adversary) is given access to an input function f via a sequence of oracles O = {O i } i&#8712;N induced by that type of adversary. For all adversarial strategies of the specified type, 1. if f &#8712; P, then T accepts with probability at least 2/3, and 2. if f is &#949;-far from P, then T rejects with probability at least 2/3, where the probability is taken over the random coins of the tester. If T works in the presence of an erasure (resp., corruption) adversary, we refer to it as an online-erasure-resilient (resp., online-corruption-resilient) tester.</p><p>If T always accepts all functions f &#8712; P, then it has 1-sided error. If T chooses its queries in advance, before observing any outputs from the oracle, then it is nonadaptive.</p><p>To ease notation, we use O(x) for the oracle's answer to query x (omitting the timestamp i). If x was queried multiple times, O(x) denotes the first answer given by the oracle.</p><p>We are now ready to prove Theorem 1.1. Let us define an important parameter, according to which we choose our strategy against the adversary: m := 4 &#8968;log(t) + 10/&#949;&#8969; .</p><p>When m &#8804; n/3 (Case I), meaning that &#949; is not too small and t is not too big, we can safely use the tester of <ref type="bibr">[BKMR24]</ref> with the parameter m above. This allows us to significantly simplify the choice of m and leads to a cleaner analysis of the tester. When m &gt; n/3 (Case II), however, we revert to sample-based testing, showing this strategy easily defeats the adversary and coincides with our desired query complexity, matching the lower bound. We analyze each of the two cases separately.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.1">Case I: m &#8804; n/3 For this case we use the following primitive from [KRV23]:</head><p>Algorithm 1: XorTest k Input : Even integer parameter k &#8805; 2 and query access to a function f : {0, 1} n &#8594; {-1, 1} 1 Query k points x 1 , . . . , x k &#8712; {0, 1}</p><p>n chosen uniformly at random (with replacement).</p><p>An improved soundness guarantee for this test was shown by [BKMR24]:</p><p>Lemma 2.1. (Soundness) If f is &#949;-far from linear, and k &#8805; 2 is even, then</p><p>The algorithm is as follows:</p><p>Algorithm 2: Online-Erasure-Resilient Linearity Tester Input : Parameters &#8712; (0, 1/2], t &#8712; N; query access to f via t-erasure oracle sequence O 1 Repeat 6 times 2 Sample X = (x 1 , . . . , x m ) &#8712; ({0, 1} n ) m uniformly at random.</p><p>3 Query f at points x 1 , . . . , x m .</p><p>4 Query f at point y = &#8853; j&#8712;S x j , where S is a uniformly random subset of [m] of size m 2 .</p><p>Reject &#9655; This implies no erasures in this iteration.</p><p>7 Accept</p><p>In this case, Algorithm 2 performs a simplified version of the tester of <ref type="bibr">[BKMR24]</ref>. We upper bound the probability of seeing an erasure at any given iteration, simplifying the analysis of <ref type="bibr">[BKMR24]</ref> for this restricted regime (in particular &#949; &#8805; &#8486;(1/n) and t &#8804; 2 O(n) ).</p><p>Lemma 2.2. If m &#8804; n/3, the probability that one specific iteration of the loop in line 1 of Algorithm 2 queries an erased point is at most 3/64.</p><p>Proof. If m &#8804; n/3, the algorithm enters the loop and queries a total of 6(m + 1) points, which induce at most 6t(m + 1) manipulations through the entire execution. We define three bad events and give upper bounds on their probabilities.</p><p>An erasure while querying X. Let B 1 be the event that O(x j ) =&#8869; for some point x j sampled in this iteration, where j &#8712; [m]. Each point x j is sampled uniformly from {0, 1} n , so the probability it is erased is at most 6t(m + 1)/2 n . By a union bound over all m points, using m &#8804; n, we have Pr</p><p>X induces a bad distribution of y points. For any choice S denote y S = &#8853; j&#8712;S x j , and let B 2 be the event that, in this iteration, there exist two different choices of S leading to the same choice y &#8712; {0, 1}</p><p>n . For any two distinct sets T 1 , T 2 &#8834; [m] of size m/2 w.l.o.g. there exists an element &#8467; &#8712; T 1 \ T 2 . Fix all entries in X besides x &#8467; . The value of y T 2 is now fixed, but over the random choice of x &#8467; &#8712; {0, 1}</p><p>n , the vector y T 1 is uniform over {0, 1} n . Thus, Pr x &#8467; [y T 1 = y T 2 ] = 2 -n and, consequently,</p><p>where both expectations are over all entries in X besides x &#8467; , which are drawn independently from x &#8467; . We use a union bound over all pairs of subsets T 1 and T 2 , and the fact m &#8804; n/3 to get</p><p>(2.4)</p><p>An erasure on query y. Let B 3 be the event that O(y) =&#8869; for the point y queried in this iteration. The adversary knows X before y is queried, but there are plenty of choices for y. Conditioned on B 2 , the distribution of y is uniform over m m/2 different choices. We use m m/2 &#8805; 2 m / &#8730; 2m, to obtain</p><p>In terms of the bad events, we wish to bound Pr[B 1 &#8746; B 3 ]. By using a union bound over B 1 and B 3 and then the law of total probability to compute Pr[B 3 ], we get</p><p>next combine the bounds from (2.3), (2.4) and (2.5), and use t &#8804; 2 m 4 -10 (which is implied by &#949; &#8804; 1/2).</p><p>where the last transition holds since (m+1)m 2 3m 4</p><p>&#8804; 3 for all positive values of m.</p><p>We are ready to prove the correctness of Algorithm 2, showing Theorem 1.1 for case I.</p><p>Proof. If Algorithm 2 entered the loop in line 1, then it makes 6(m + 1) = O(log t + 1/&#949;) queries.</p><p>We next analyse the algorithm in the presence of erasures. It is easy to see the algorithm always accepts all linear functions. Now, fix an adversarial (budget-managing) strategy and suppose that the input function is &#949;-far from linear. By Lemma 2.1 and since k = m/2 &#8805; 1/&#949; is even, the probability that one iteration of the loop in line 1 samples a witness of nonlinearity is at least min {1/4 , k&#949;/2} &#8805; min {1/4 , 1/2} = 1/4. By Lemma 2.2, the probability that an erasure is seen in a specific iteration is at most 1/16. By a union bound, the probability of a single iteration seeing an erasure or not selecting a witness of nonlinearity is at most 1 -1 4 + 1 16 = 1 -3 16 . Algorithm 2 errs only if this occurs in all iterations. By independence of random choices in different iterations, the failure probability is at most</p><p>where we used 1 -x &#8804; e -x for all x.</p><p>Finally, we show that Algorithm 2 has two-sided error at most 1/3 in the presence of corruptions. The soundness holds with the same analysis, as finding a single violation suffices for this case. For completeness, note that the algorithm can only err if it has seen a manipulation, and the probability of seeing a manipulation at any iteration is at most 3/64 by Lemma 2.2. Using a union bound over all 6 iterations, the overall probability of seeing any manipulated entry during the entire execution is at most 6 &#8226; (3/64) &#8804; 1/3.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.2">Case II: m &gt; n/3</head><p>In this case, we use [GR16, Theorem 5.1] for the domain {0, 1}</p><p>n and run an algorithm that only uses random samples, their algorithm is simple, and we bring it here for completeness:</p><p>&#9655; w.h.p. this doesn't happen; 4 Let Y &#8834; X be an arbitrary basis for {0, 1}</p><p>n and g : {0, 1} n &#8594; {0, 1} the unique linear function that agrees with f on all points in Y .</p><p>8 Accept.</p><p>Lemma 2.3. ( [GR16, Theorem 5.1 (1)], for Boolean functions) There is a one-sided error sample-based tester of sample complexity O(1/&#949; + n) for testing linearity of functions of the form f : {0, 1} n &#8594; {0, 1}.</p><p>Next, we show that if the algorithm uses only uniform random samples, then the adversary loses its power, in the sense that we, most likely, won't see any manipulation.</p><p>Theorem 2.1. Let T be a sample-based tester (for some property P) with input length N and distance &#949; that uses q uniformly random samples and succeeds with probability 1 -&#948;. Then the same tester with the same number of queries succeeds with probability 1 -2&#948; in the presence of t-online-manipulation adversary for any t &#8804; &#948; &#8226; N/q<ref type="foot">foot_1</ref> . Proof. To analyze the tester, we note that all queries in this test are random samples, and the total number of manipulations made is qt. Therefore, each sample has probability of at most qt/N to see an erasure. By a union bound over all the samples taken, the overall probability to sample any previously-manipulated points is at most q 2 t/N &#8804; &#948;. Adding this error to the original error of the tester T completes the proof.</p><p>Remark 2.1. If T is a one-sided error tester, we can keep it one-sided against online-erasure adversary by accepting whenever we see an erasure. Otherwise, we get a two-sided error tester.</p><p>Corollary 2.1. There is a one-sided error sample-based tester for testing linearity against online-erasure adversaries that uses q = O(1/&#949; + n) queries, succeeds with probability 2/3 and works for all &#949; &#8712; (0, 1/2) and t &#8804; O(min 2 n /n 2 , &#949; 2 2 n ).</p><p>We are now ready to prove Theorem 1.1 for Case II.</p><p>Proof. The query complexity is q = O(n + 1/&#949;), and in our case, it is at most O(m + 1/&#949;) = O(log t + 1/&#949;).</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.3">A testing impossibility result</head><p>In this section we prove Theorem 1.2, that is that testing is impossible when t is too large, by showing a much more general statement. The argument below is formulated for properties of functions f : F n q &#8594; F q , but can be adjusted to other settings as well (e.g., properties of strings, &#931; n ). The proof leverages a recent elegant argument of <ref type="bibr">[Fis24]</ref>, that shows c/&#949; queries do not suffice to &#949;-test a property P, provided the testing task is not trivial (the precise will appear shortly).</p><p>Consider any such non-trivial task in the online manipulation model with large enough t (roughly &#949; 2 -fraction of the input size). On the one hand, after c/&#949; the tester still cannot distinguish certain YES and NO instances with high enough probability. On the other hand, at this point an online adversary can already manipulate an &#949;-fraction of the original input, enough to completely erase the initial difference between a YES and a NO instance. Hence, any additional query is useless, and the tester is doomed to fail.</p><p>We first review the argument of <ref type="bibr">[Fis24]</ref> in the offline model and some of its notations, and later state and prove the impossibility result for the online model.</p><p>The offline model. We consider properties of functions 2 f : F n q &#8594; F q , where a property P is identified with a subset of all these functions. Fix a property P such that there exists two input functions F YES &#8712; P and F NO that is &#945;-far from P for some constant &#945; &gt; 0. For simplicity, assume the proximity parameter satisfies &#949; = &#8467;/q n &gt; 0 for some integer &#8467; &#8712; N.</p><p>First, we consider a function G &#8712; P that minimizes the distance to f NO (if such G is not unique, choose one arbitrarily), and denote by D &#8838; F n q the set of inputs on which G and F NO disagree. For any A &#8838; D, define</p><p>In particular, G D &#8801; F NO , and G &#8709; &#8801; G, and evidently G A has distance exactly |A| /q n from the property P (since G minimizes the distance of F NO from P).</p><p>The focus from now on is on a task we call (G, D, &#8467;)-testing. An algorithm solves this task if it accept G with probability at least 2/3, but accepts G A with probability at most 1/3 for any A &#8838; D such that |A| = &#8467;. In particular, for &#949; = &#8467;/q n , an &#949;-tester for P is a (G, D, &#8467;)-tester.</p><p>It was shown in <ref type="bibr">[Fis24]</ref> that w.l.o.g, a randomized (G, D, &#8467;)-tester is non-adaptive and only queries points in D. Thus, any such tester simply queries the function on q points x 1 , . . . x q , where each x i is a random variable supported on D. Furthermore, for each point z &#8712; D we can define the event E z that the point z was queried (i.e,</p><p>Denoting by D &#8242; = {z 1 , . . . , z &#8467; } the set with &#8467; points that has the smallest probabilities (break ties arbitrarily), we can bound the probability of the event E D &#8242; that any point from D &#8242; was queried. By a union bound, we have</p><p>Since we started with f NO that is &#945;-far from P, we have |D| &#8805; &#945; &#8226; q n as well as &#8467; = &#949; &#8226; q n . Hence</p><p>Pr</p><p>To finish up, consider two executions of the tester with the same random coins, one when fed values from G and another when fed values from G D &#8242; . The answer can only differ if the event E D &#8242; occurred (otherwise, all the oracle answers are the same for both inputs). Thus, the probabilities of acceptance can differ by at most Pr [E D &#8242; ], which leads to a contradiction if q &lt; &#945;/(3&#949;).</p><p>The online model. For the online model, we similarly begin from a guaranteed function f NO that is &#945;-far, and a closest function G &#8712; P (arbitrarily chosen if not unique) that differs on the set of inputs D &#8838; F n q . We consider the same task of (U, D, &#8467;)-testing, where we assumed &#949; = &#8467;/q n &#8712; (0, &#945;).</p><p>We denote F n := f : F n q &#8594; F q and F = &#8746; n&#8712;N F n . A property is simply P &#8838; F, and we use P n = P &#8745; F n . We have the following formal statement: Theorem 2.2. Fix a constant &#945; &gt; 0, and a property P &#8838; F, such that for infinitely many values of n there exist F n YES &#8712; P n and f n NO that is &#945;-far from P. Fix &#949; = &#8467;/q n &lt; &#945; for some integer &#8467; &#8712; N, and t = (10/&#945;)&#949; 2 q n . Then there is not &#949;-tester for P that is resilient to t manipulations per query.</p><p>Proof. The argument begins as before. For any n we define G &#8712; mathcalP n , and D that depend on f n NO . Any &#949;tester for P is also a (U, D, &#8467;)-tester as defined above. Assume such a tester exists and is resilient to t manipulations per query.</p><p>Similarly to before, we define an event for each point z &#8712; D, but these events focus only on the first queries. Define E z to be the event that z is queried within the first q 0 = &#945;/(10&#949;) queries by the tester. As before, we can order the points z by the probabilities of E z and define a set D &#8242; &#8838; D consisting of the &#8467; points with minimal probabilities. The event that any of these point was queried within the first q 0 queries is denoted by E D &#8242; and satisfies</p><p>Pr [E D &#8242; ] &#8804; &#949; &#8226; q 0 &#945; &lt; 1 10 .</p><p>As before, fix the random coins of a tester, and consider one execution on G and another on G D &#8242; . Only now, while the tester executes, an online adversary manipulates the inputs. The adversary will simply manipulate the points in D &#8242; , of which there are exactly &#8467;. Indeed, by the time q 0 queries has been made, the adversary can manipulate all entries in D &#8242; since</p><p>For both executions on G and on G D &#8242; , the adversary acts the same. An erasing adversary will erase all entries in D &#8242; , whereas a manipulation adversary will fix their values to those of G. All in all, for any value of the random points, the tester can only see a difference between an execution on G and one on G D &#8242; if the event E D &#8242; occurred. Over all random choices, we have Pr [E D &#8242; ] &#8804; 1/(10), and since the tester must accept G with probability at least 2/3 it also falsely accepts G D &#8242; with probability at least 2/3 -1/(10) &gt; 1/3. In contradictions.</p><p>To summarize, the task of (U, D, &#8467;)-testing is impossible against t-manipulation adversary for infinitely many values of n, and so is the task of &#949;-testing the property P.</p><p>To prove Theorem 1.2, we simply apply the theorem with q = 2 and &#945; = 1/2, as for any n &#8805; 1, the affine non-linear function 1 + x 1 has distance 1/2 from linearity.</p><p>No case: f is &#949;-far from all additive functions. If Algorithm 5 rejects f w.p. &gt; 2/3, we are done. Otherwise by Lemma 3.1, we have: g is a well defined, additive function on R n , so &#948; (f, g) &#8805; &#949;. And again by Lemma 3.1, for every p &#8712; R n we have </p></div><note xmlns="http://www.tei-c.org/ns/1.0" place="foot" xml:id="foot_0"><p>Downloaded 09/04/25 to 67.189.222.199 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy</p></note>
			<note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="2" xml:id="foot_1"><p>The original argument in<ref type="bibr">[Fis24]</ref> is applied to properties of &#931; n , or equivalently functions f : [n] &#8594; &#931;. We use a slightly different to comply with linearity testing.</p></note>
		</body>
		</text>
</TEI>
