On Optimal Testing of Linearity

Esty Kelman; Uri Meir; Vipul Arora

REVIEW 2 major objections 4 minor 26 references

On Optimal Testing of Linearity

T0 review · 2 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper gives optimal linearity testers that tolerate online manipulation for almost the full range of budgets, and cuts real-domain linearity testing to O(1/ε) queries.

desk verdict The online-manipulation half is solid and new; the real-valued additivity theorem has a completeness bug that needs fixing before it is true as stated. read the letter →

arxiv 2411.14431 v1 pith:RA6AJOLP submitted 2024-11-21 cs.CC cs.DS

Vipul Arora , Esty Kelman , Uri Meir This is my paper · ORCID

classification cs.CCcs.DS

keywords linearitytestingpropertyonlinemanipulationssample-basedself-correctiondistribution-freelow-degree

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Linearity testing asks whether a function is linear or far from every linear function using as few oracle calls as possible. This paper solves two open versions of that question. In the online-manipulation model, where an adversary can erase or corrupt up to $t$ input entries after every query, it constructs an $\varepsilon$-tester with $O(\max\{1/\varepsilon, \log t\})$ queries for all $t$ up to $c\cdot\min\{\varepsilon^2, 1/n^2\}\cdot 2^n$, and proves that no tester exists once $t$ reaches $20\varepsilon^2 2^n$; the two bounds are tight up to constants. The key move is a regime switch: for small $t$ use a simplified $k$-point test, and for large $t$ switch to sample-based testing, which is automatically robust to manipulation. Over the reals, the paper removes the extra $\log(1/\varepsilon)$ factor from distribution-free linearity/additivity testing, giving $O(1/\varepsilon)$ queries, by observing that each evaluation of the self-corrected function only needs to succeed with constant probability. The same modification improves distribution-free low-degree polynomial testing to $O(d^5 + d^2/\varepsilon)$ queries for constant degree $d$.

What carries the argument

The machinery is a pair of regime-shifting primitives plus a self-correction object. $\mathrm{XorTest}_k$, the $k$-point test, chooses $k$ random points and checks the parity constraint $f(\oplus_i x_i)=\prod_i f(x_i)$; its rejection probability is amplified by a factor $\approx k$ over the 3-point test, which is what makes $O(\log t + 1/\varepsilon)$ queries attainable when $t$ is small. Sample-based testing, in the form of the Goldreich--Ron tester, draws $\Theta(n+1/\varepsilon)$ uniformly random labeled samples and either extrapolates a linear function from a basis or rejects; because all queries are random and independent of previous answers, the probability that any sample lands on an adversarially manipulated coordinate is at most $q^2 t/2^n$, so the adversary is neutralized for large $t$. Over the reals, the central object is the self-corrected function $g(p)=\mathrm{maj}_{x\sim N(0,I)} \kappa_p (f(p/\kappa_p - x)+f(x))$, where $\kappa_p$ radially contracts $p$ into a small ball; a single random direction $x$ gives the 'opinion' $g_x(p)$, and the paper shows one such opinion is enough per test point. The impossibility direction uses Fischer's hard-distribution argument, which concentrates on the $\ell$ least-queried disagreement points and lets the adversary hide them within the manipulation budget.

What would settle it

Take a discontinuous additive $f:\mathbb{R}\to\mathbb{R}$ (a Hamel-basis construction) and let $D$ be a point mass at some $p$ with $f(p)\neq g(p)$, where $g$ is the self-corrected function of (6)--(7). Run Algorithm 5; since a one-sided tester must accept every valid additive input with probability 1, any rejection -- in particular from Algorithm 6's third test, which can fail for such $f$ -- falsifies the one-sided additivity guarantee in Theorem 1.3.

Watch

Extended reading notes

Core claim

The paper's central claim is a doubly optimal result for linearity over $\mathbb{F}_2$ in the online-manipulation model: for every budget $t \le c\cdot\min\{\varepsilon^2, 1/n^2\}\cdot 2^n$ there is an $\varepsilon$-tester making $O(\max\{1/\varepsilon, \log t\})$ queries, and for $t \ge 20\varepsilon^2 2^n$ no $\varepsilon$-tester exists. The upper bound reuses [BKMR24]'s $k$-point test in the small-$t$ regime and switches to Goldreich--Ron sample-based testing in the large-$t$ regime, where the sample complexity $\Theta(n+1/\varepsilon)$ coincides with $\Theta(\log t + 1/\varepsilon)$. The impossibility extends Fischer's hard-distribution argument to show that any property with a YES instance and a constant-far NO instance becomes untestable once the adversary can manipulate an $\varepsilon$-fraction of the input within the tester's first $O(1/\varepsilon)$ queries. Over the reals, the paper claims a one-sided-error distribution-free $O(1/\varepsilon)$-query tester for additivity and for linearity of continuous functions, improving Fleming--Yoshida's $O((1/\varepsilon)\log(1/\varepsilon))$; the proof's insight is that a correct evaluation of the self-corrected function $g$ at a single witness point with constant probability is enough, since the other evaluations may be erroneous. The same repair removes the $\log(1/\varepsilon)$ factor from the degree-$d$ polynomial testers of [ABF+23].

Load-bearing premise

For the real additivity tester to keep one-sided error, every additive function must agree with its self-corrected version on the checked points; the paper only proves this for linear functions, and additive-but-not-linear functions can violate it.

Editorial extensions

If this is right

Linearity over $\mathbb{F}_2$ is testable with $O(\log t + 1/\varepsilon)$ queries against budget-managing online adversaries for every $t \le c\cdot\min\{\varepsilon^2,1/n^2\}\cdot 2^n$, which is the largest manipulation budget for which testing is possible up to constants.
Any property that has a YES instance and a constant-far NO instance becomes untestable in the online model once $t \ge (10/\alpha)\varepsilon^2 N$, so the impossibility is not special to linearity.
Distribution-free additivity and linearity of continuous functions over $\mathbb{R}$ admit one-sided-error testers with $O(1/\varepsilon)$ queries, removing the $\log(1/\varepsilon)$ factor from the previous real-domain testers.
The same $O(1/\varepsilon)$ query bound is obtained for distribution-free testing of degree-$d$ polynomials over the reals for constant $d$, including the approximate and rational-lattice variants.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Beyond the paper, the regime-switch principle is likely portable: any property with an optimal sample-based tester and a $k$-point-style combination test should inherit a doubly optimal online tester with the same threshold $t\approx\Theta(\varepsilon^2 N)$.
Beyond the paper, the observation that a constant-probability-correct self-correction suffices suggests that other algorithms amplifying an inner self-corrector to error $1-O(\varepsilon)$ only for a union bound can drop that amplification, potentially improving related distribution-free tests.
A concrete scope check: if Theorem 1.3 is interpreted literally for additivity, it must accept all Hamel-basis additive functions; testing Algorithm 5 on a discontinuous additive function would settle whether the one-sided guarantee is real or only holds for linear inputs.
The impossibility threshold $t=\Theta(\varepsilon^2 N)$ draws a clean line: below it linearity is testable with optimal queries, at it every property with a constant-far NO instance becomes untestable, so the online model offers no intermediate regime for such properties.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things to know. First, the online-manipulation half is the real contribution: the sample-based tester observation is clean, and the matching impossibility for t >= 20ε^2·2^n rounds out the story nicely. I think that half is correct. Second, the real-valued half has a genuine completeness bug: Theorem 1.3's additivity claim is not proved for all additive functions, and as stated I suspect it is false.

What's new and good: Theorem 1.1 covers essentially the full range of t, up to constants; the simplification of the BKMR tester in Case I is sensible and the proof of Lemma 2.4 is careful. The use of Goldreich-Ron sample-based testers to weather an online adversary is an elegant idea, and Theorem 2.6 is a generally useful statement. The impossibility argument via Fischer's lower-bound formalism is coherent and gives the right constant-factor threshold. If I were refereeing, I'd be happy with this part.

The soft spot: the additivity tester in Section 3.1. The completeness proof explicitly handles only linear f. But the theorem promises additivity, and the authors themselves cite Hamel for non-linear additive functions. For any additive f, the self-correction in (6) simplifies to g_x(p) = κ_p f(p/κ_p). For linear f this equals f(p); for non-linear additive f it does not, except possibly on a measure-zero set, because κ_p is a real scalar, not rational. So the tester can reject a valid additive input with probability close to 1 if the distribution D has mass outside the small ball. That is not a minor gap: it breaks the one-sided error claim and likely the two-sided guarantee as well. The soundness side is fine—the invocation of Lemma 3.1 is legitimate once Algorithm 6 accepts with probability at least 1/3, so the stress-test's inconsistency worry there doesn't land. The problem is purely completeness (and the theorem's statement). The linearity-for-continuous-functions version may survive, and the low-degree results (Theorem 1.4) look okay because the property there is polynomial, not additive pathologies.

Bottom line: this paper deserves a serious referee, but the real-valued additivity theorem should be corrected or the paper should restrict Theorem 1.3 to continuous/additive-linear functions. I'd send it to review with that caveat, and I'd cite the online-manipulation results in my own work.

Referee Report

2 major / 4 minor

Summary. The paper studies linearity testing in two distinct settings. In the online manipulation model over F2 (Section 2), it presents a query-optimal tester resilient to t online manipulations per query for all t ≤ c·min{ε^2, 1/n^2}·2^n, combining a simplified k-point tester for small t and a sample-based tester for large t, and proves an impossibility result for t ≥ 20ε^2·2^n. In the distribution-free setting over the reals (Section 3), the paper claims O(1/ε)-query testers for additivity and for linearity of continuous functions, improving the Fleming-Yoshida tester, and extends the technique to degree-d polynomial testing with O(d^5 + d^2/ε) queries.

Significance. The online manipulation results are the strongest contribution: Theorem 1.1 gives a doubly optimal tester, and the sample-based tester observation (Theorem 2.6) is clean and useful. The impossibility result is a natural complement. The real-valued results, if correct, would be optimal and would simplify prior work. However, the additivity part of Theorem 1.3 has a serious gap in its one-sided error guarantee, and the linearity part is asserted without a complete proof. The low-degree tester (Theorem 1.4) appears sound and is a nice improvement. Overall, the paper contains significant and correct results in the online model, but the claims for additivity testing over the reals require major revision.

major comments (2)

[§3.1, Theorem 1.3 (additivity claim)] The one-sided error guarantee for additivity is not established and, as stated, is incorrect. The completeness proof covers only linear functions: 'if f is linear, Algorithm 6 always accepts, and moreover, (i) g≡f and (ii) for all p,x∈R^n, g(p)=g_x(p), ensuring Algorithm 5 also accepts f.' Additive non-linear functions exist via Hamel bases. For such f, Eq. (6) gives g_x(p)=κ_p f(p/κ_p). When ||p||_2>1/50, κ_p=50||p||_2 is generally irrational, so f(p/κ_p) need not equal f(p)/κ_p, and hence g_x(p) need not equal f(p). If the unknown distribution D is a point mass at such a p, Algorithm 5 line 5 rejects with probability 1 on a valid additive input. Lemma 3.1 only guarantees that g is additive and that g_x(p) agrees with g(p) with probability >1/2; it does not imply g(p)=f(p). A separate completeness argument for all additive functions, or a change of the theorem statement to two-sided error, is required.
[§3.1, Theorem 1.3 (linearity claim)] The linearity part of Theorem 1.3 is asserted but not proved. The text says 'the tester for linearity follows from the same arguments as in [FY20] where one uses our modified query-g subroutine in both their testers.' The additivity soundness proof relies on the fact that g is additive and f is ε-far from all additive functions, so that Pr_{p∼D}[f(p)≠g(p)]≥ε. For linearity, Lemma 3.1 only guarantees that g is additive, not linear, and f is only assumed ε-far from all linear functions, so the analogous step does not apply. The paper should either provide the precise FY20 argument adapted to the modified subroutine, or state explicitly which additional conditions (e.g., continuity of f) are used and how the constant-accuracy evaluation suffices.

minor comments (4)

[§3.2, Claim 3.5] The sentence 'we have g_q(c_i p)≠g(c_i p) with probability most 1 − 1/(7d)' should read 'with probability at most 1/(7d)', or equivalently 'g_q(c_i p)=g(c_i p) with probability at least 1−1/(7d)'. The subsequent union bound uses the correct bound.
[§2.2, Algorithm 3] The line 'Accept if span(X)≠{0,1}^n' is confusing, as it appears to accept when the sample does not span the whole space. The accompanying comment 'w.h.p. this doesn't happen' clarifies the intent, but the line should be rephrased and the role of this fallback acceptance should be explained.
[§2, heading and text] The surname is misspelled as 'Kalmaj' in the Section 2 heading and in the text; the correct spelling is 'Kalemaj', matching the reference [KRV23].
[§3.2, Theorems 3.6 and 3.7] These theorems are stated with proofs omitted. While they are said to follow from the same arguments as Theorem 1.4, the omission makes them difficult to verify, especially given the gap in Theorem 1.3. Please provide at least proof sketches.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the new results are proved from externally published lemmas; the only flagged issue in Theorem 1.3 is a completeness gap, not a derivation loop.

full rationale

At every load-bearing step the derivation imports an external, published theorem rather than assuming its own conclusion. Lemma 2.3 (BKMR24) supplies the k-point soundness used in Case I of Theorem 1.1; Lemma 2.5 (GR16) supplies the sample-based base tester for Case II; Theorem 2.6 is a new but self-contained reduction that does not presuppose testability; Theorem 2.8 adapts Fischer's external lower-bound argument; Lemma 3.1 (FY20) and Lemma 3.4 (ABF+23) supply the self-corrector guarantees for the real-valued and low-degree testers. That BKMR24 and ABF+23 share authors with the present paper is normal and not disqualifying: both are published theorems with assumptions that do not include the present target results, so they are independent evidence. The one genuine weakness is in the proof of Theorem 1.3: the completeness argument explicitly handles only 'if f is linear, Algorithm 6 always accepts, and moreover (i) g≡f ... ensuring Algorithm 5 also accepts f,' while the theorem promises one-sided error for all additive functions. For a Hamel-type additive non-linear f, the equality g(p)=f(p) is not established (and need not hold), so the one-sided-error guarantee for additivity is not proved as written. This is a correctness/completeness gap, not a circular reduction: the conclusion is not being fed back as an input, and no equation in the paper makes the additive claim equal to its premise by construction. Hence circularity score 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The paper's central claims rest on imported lemmas from BKMR24, FY20, ABF+23, and Fischer. These are external published results, not derived in this manuscript. The additivity completeness additionally depends on an unstated property of non-linear additive functions, which is the main fragility.

assumptions (6)

standard math Lemma 2.3: the k-point test rejects ε-far functions with probability at least min{1/4, kε/2}.
Imported from BKMR24 and used as the soundness engine in Case I of the online model.
domain assumption Lemma 3.1: if the characterization subroutine accepts with probability at least 1/10, the self-corrected function g is well-defined and additive, and each random opinion g_x(p) is correct with probability at least 1/2.
Imported from FY20; underlies the O(1/ε) real-valued tester; its scope for non-linear additive functions is not examined in the paper.
standard math Lemma 3.4: for low-degree self-correction from ABF+23, if the characterization test fails with probability at most 2/3 then g is a degree-d polynomial and random opinions are correct with probability at least 1 - 1/(7d).
Imported from ABF+23 and used in Theorem 1.4.
standard math Fischer's lower bound argument: any tester for a property with a far pair induces a hard distribution and requires Ω(1/ε) queries.
Used in the impossibility theorem for the online manipulation model.
domain assumption The online manipulation model (Definition 2.1) with budget-managing adversaries as the threat model.
The theorem statements are contingent on this specific adversarial model.
domain assumption Non-linear additive functions over R exist and satisfy f(x+y)=f(x)+f(y) but not f(p/κ)=f(p)/κ for real κ.
Used implicitly in Section 3.1; the proof of one-sided error for additivity would need to rule out rejection of such functions.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On Optimal Testing of Linearity." pith.science (2026). https://pith.science/paper/RA6AJOLP

@misc{pith2026241114431,
  author       = {Pith},
  title        = {Pith review of: On Optimal Testing of Linearity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RA6AJOLP}},
  note         = {Machine review of arXiv:2411.14431}
}

abstract

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 manipulations model introduced by Kalemaj, Raskhodnikova and Varma (ITCS 2022 \& 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 their approach fails if $t$ is too large. We extend this result, showing an optimal tester for almost any possible value of $t$. First, we simplify their result when $t$ is small, 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 \emph{very} large, any reasonable property, and in particular linearity, cannot be tested at all. Second, we consider linearity over the reals with proximity parameter $\varepsilon$. Fleming and Yoshida (ITCS 2020) gave a tester using $O(1/\varepsilon\ \cdot log(1/\varepsilon))$ queries. We simplify their algorithms and modify the analysis accordingly, showing an optimal tester that only uses $O(1/\varepsilon)$ 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 degree $d$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 23 canonical work pages

[1]

Low degree testing over the reals

Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, and Yuichi Yoshida. Low degree testing over the reals. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023 , pages 738--792. SIAM , 2023

work page 2023
[2]

Kiwi, and Madhu Sudan

Mihir Bellare, Don Coppersmith, Johan H stad, Marcos A. Kiwi, and Madhu Sudan. Linearity testing in characteristic two. IEEE Transactions on Information Theory , 42(6):1781--1795, 1996

work page 1996
[3]

Free bits, PCP s, and nonapproximability-towards tight results

Mihir Bellare, Oded Goldreich, and Madhu Sudan. Free bits, PCP s, and nonapproximability-towards tight results. SIAM Journal on Computing (SICOMP) , 27(3):804--915, 1998

work page 1998
[4]

Property testing with online adversaries

Omri Ben-Eliezer , Esty Kelman, Uri Meir, and Sofya Raskhodnikova. Property testing with online adversaries. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) . Schloss-Dagstuhl-Leibniz Zentrum f \"u r Informatik, 2024

work page 2024
[5]

Self-testing/correcting with applications to numerical problems

Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. Journal of Computer and System Sciences , 47(3):549--595, 1993

work page 1993
[6]

Improved non-approximability results

Mihir Bellare and Madhu Sudan. Improved non-approximability results. In Proceedings, ACM Symposium on Theory of Computing (STOC) , pages 184--193, 1994

work page 1994
[7]

Vadhan, and Avi Wigderson

Eli Ben - Sasson, Madhu Sudan, Salil P. Vadhan, and Avi Wigderson. Randomness-efficient low degree tests and short PCP s via epsilon-biased sets. In Proceedings, ACM Symposium on Theory of Computing (STOC) , pages 612--621, 2003

work page 2003
[8]

Interactive proofs and the hardness of approximating cliques

Uriel Feige, Shafi Goldwasser, L \' a szl \' o Lov \' a sz, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the ACM , 43(2):268--292, 1996

work page 1996

Show all 26 references

[9]

A basic lower bound for property testing

Eldar Fischer. A basic lower bound for property testing. arXiv preprint arXiv:2403.04999 , 2024

2024 arXiv
[10]

Distribution-Free Testing of Linear Functions on R ^n

Noah Fleming and Yuichi Yoshida. Distribution-Free Testing of Linear Functions on R ^n . In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA , volume 151 of LIPIcs , pages 22:1--22:19. ...

2020
[11]

Property testing and its connection to learning and approximation

Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. Journal of the ACM , 45(4):653--750, 1998

1998
[12]

On sample-based testers

Oded Goldreich and Dana Ron. On sample-based testers. ACM Transactions on Computation Theory (TOCT) , 8(2):1--54, 2016

2016
[13]

Eine basis aller zahlen und die unstetigen l \"o sungen der funktionalgleichung: f (x+ y)= f (x)+ f (y)

Georg Hamel. Eine basis aller zahlen und die unstetigen l \"o sungen der funktionalgleichung: f (x+ y)= f (x)+ f (y) . Mathematische Annalen , 60(3):459--462, 1905

1905
[14]

Distribution-free property-testing

Shirley Halevy and Eyal Kushilevitz. Distribution-free property-testing. SIAM Journal on Computing , 37(4):1107--1138, 2007

2007
[15]

Simple analysis of graph tests for linearity and PCP

Johan H stad and Avi Wigderson. Simple analysis of graph tests for linearity and PCP . Random Structures and Algorithms , 22(2):139--160, 2003

2003
[16]

Breaking the epsilon-soundness bound of the linearity test over GF(2)

Tali Kaufman, Simon Litsyn, and Ning Xie. Breaking the epsilon-soundness bound of the linearity test over GF(2) . SIAM Journal on Computing (SICOMP) , 39(5):1988--2003, 2010

1988
[17]

Sublinear-time computation in the presence of online erasures

Iden Kalemaj, Sofya Raskhodnikova, and Nithin Varma. Sublinear-time computation in the presence of online erasures. Theory of Computing , 19(1):1--48, 2023

2023
[18]

Adversarial low degree testing

Dor Minzer and Kai Zhe Zheng. Adversarial low degree testing. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024 , pages 4395--4409. SIAM , 2024

2024
[19]

Linearity testing/testing H adamard codes

Sofya Raskhodnikova and Ronitt Rubinfeld. Linearity testing/testing H adamard codes. In Encyclopedia of Algorithms , pages 1107--1110. Springer, 2016

2016
[20]

Rubinfeld and M

R. Rubinfeld and M. Sudan. Robust characterization of polynomials with applications to program testing. SIAM Journal on Computing (SICOMP) , 25:647--668, 1996

1996
[21]

Low-degree tests at large distances

Alex Samorodnitsky. Low-degree tests at large distances. In Proceedings, ACM Symposium on Theory of Computing (STOC) , pages 506--515, 2007

2007
[22]

Probabilistically checkable proofs with low amortized query complexity

Madhu Sudan and Luca Trevisan. Probabilistically checkable proofs with low amortized query complexity. In Proceedings, IEEE Symposium on Foundations of Computer Science (FOCS) , pages 18--27, 1998

1998
[23]

A PCP characterization of NP with optimal amortized query complexity

Alex Samorodnitsky and Luca Trevisan. A PCP characterization of NP with optimal amortized query complexity. In Proceedings, ACM Symposium on Theory of Computing (STOC) , pages 191--199, 2000

2000
[24]

Gowers uniformity, influence of variables, and PCP s

Alex Samorodnitsky and Luca Trevisan. Gowers uniformity, influence of variables, and PCP s. SIAM Journal on Computing (SICOMP) , 39(1):323--360, 2009

2009
[25]

Derandomizing homomorphism testing in general groups

Amir Shpilka and Avi Wigderson. Derandomizing homomorphism testing in general groups. SIAM Journal on Computing (SICOMP) , 36(4):1215--1230, 2006

2006
[26]

Recycling queries in PCP s and in linearity tests (extended abstract)

Luca Trevisan. Recycling queries in PCP s and in linearity tests (extended abstract). In Proceedings, ACM Symposium on Theory of Computing (STOC) , pages 299--308, 1998

1998

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

Low degree testing over the reals

Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, and Yuichi Yoshida. Low degree testing over the reals. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023 , pages 738--792. SIAM , 2023

work page 2023

[2] [2]

Kiwi, and Madhu Sudan

Mihir Bellare, Don Coppersmith, Johan H stad, Marcos A. Kiwi, and Madhu Sudan. Linearity testing in characteristic two. IEEE Transactions on Information Theory , 42(6):1781--1795, 1996

work page 1996

[3] [3]

Free bits, PCP s, and nonapproximability-towards tight results

Mihir Bellare, Oded Goldreich, and Madhu Sudan. Free bits, PCP s, and nonapproximability-towards tight results. SIAM Journal on Computing (SICOMP) , 27(3):804--915, 1998

work page 1998

[4] [4]

Property testing with online adversaries

Omri Ben-Eliezer , Esty Kelman, Uri Meir, and Sofya Raskhodnikova. Property testing with online adversaries. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) . Schloss-Dagstuhl-Leibniz Zentrum f \"u r Informatik, 2024

work page 2024

[5] [5]

Self-testing/correcting with applications to numerical problems

Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. Journal of Computer and System Sciences , 47(3):549--595, 1993

work page 1993

[6] [6]

Improved non-approximability results

Mihir Bellare and Madhu Sudan. Improved non-approximability results. In Proceedings, ACM Symposium on Theory of Computing (STOC) , pages 184--193, 1994

work page 1994

[7] [7]

Vadhan, and Avi Wigderson

Eli Ben - Sasson, Madhu Sudan, Salil P. Vadhan, and Avi Wigderson. Randomness-efficient low degree tests and short PCP s via epsilon-biased sets. In Proceedings, ACM Symposium on Theory of Computing (STOC) , pages 612--621, 2003

work page 2003

[8] [8]

Interactive proofs and the hardness of approximating cliques

Uriel Feige, Shafi Goldwasser, L \' a szl \' o Lov \' a sz, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the ACM , 43(2):268--292, 1996

work page 1996