pith. sign in

arxiv: 2605.22813 · v1 · pith:XS7QSQEUnew · submitted 2026-05-21 · 💻 cs.DS

Optimal Testing of Reed-Muller Codes with an Online Adversary

Esty Kelman , Uri Meir , Kai Zhe Zheng This is my paper

Pith reviewed 2026-05-22 02:50 UTC · model grok-4.3

classification 💻 cs.DS
keywords Reed-Muller codesproperty testingonline-erasure modelquery complexitysemi-sample-based testerslifted codes
0
0 comments X

The pith

Semi-sample-based testers achieve optimal query complexity for Reed-Muller codes even against an online adversary that erases points after each query.

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

The paper defines semi-sample-based testers that first select a fixed subset of the domain and then issue queries uniformly at random inside that subset. This hybrid approach is shown to preserve soundness when an adversary erases up to t points after every query. The resulting testers decide whether an input function over a finite field is a Reed-Muller codeword or far from all such codewords while using the fewest queries possible in this adversarial setting. The same construction supplies the first known testers for lifted affine-invariant codes under online erasures.

Core claim

Semi-sample-based testers for Reed-Muller codes achieve optimal query complexity in the online-erasure model by proving that their soundness analysis continues to hold when an adversary erases up to t points after each query and the initial subset is chosen without knowledge of those erasures.

What carries the argument

Semi-sample-based tester: a procedure that selects a subset S of the domain in advance and then draws queries uniformly at random inside S, thereby limiting the adversary's ability to target future queries.

If this is right

  • Optimal query complexity is obtained for Reed-Muller code testing in the online-erasure model.
  • The same testers give the first known algorithms for lifted affine-invariant codes under online erasures.
  • The construction improves the query bound previously known for this setting.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The precommitment-to-a-subset idea may extend to testing other algebraic properties when queries must be issued before erasures are revealed.
  • Similar hybrids could be examined for constant-query regimes or for different erasure budgets t relative to the domain size.
  • One could test whether the same soundness carries over when the subset S is allowed to depend on a small number of initial non-erased samples.

Load-bearing premise

The soundness analysis of semi-sample-based testers continues to hold when an adversary erases up to t points after each query and the initial subset S is chosen without knowledge of the erasures.

What would settle it

A function that is far from every Reed-Muller codeword yet is accepted by the semi-sample-based tester with probability noticeably above the soundness threshold, even after the adversary erases t points following each query.

read the original abstract

Motivated by applications to property testing in the online-erasure model of Kalemaj, Raskhodnikova, and Varma (ITCS 2022 and Theory of Computing 2023), we define and analyze {\em semi-sample-based testers} for Reed-Muller codes. The task in Reed-Muller testing is to determine whether an input function $f: \F^n \to \F$ belongs to the Reed-Muller code or is far from it, using as few point queries to $f$ as possible. Reed-Muller testing is a well-studied task with its roots in both the Property Testing and Probabilistically Checkable Proofs literature. The online-erasure model introduces a twist: after each query made, an adversary may erase up to $t$ points of the input function, potentially thwarting any test in which the queries follow a predictable pattern. Semi-sample-based testers are a hybrid between sample-based testers -- which can only make uniformly random queries to the input function -- and standard testers, which can choose their queries freely. They are designed with the online-erasure model in mind and operate by first choosing some subset $S$ of the domain and then making their queries uniformly at random inside of $S$. We describe semi-sample-based testers for the Reed-Muller code and give an optimal analysis of their soundness. Consequently, we show that semi-sample-based testers are indeed effective in the presence of online erasures, and thereby achieve optimal query complexity for testing the Reed-Muller code in the online-erasure model. This result improves upon prior work of Minzer and Zheng (SODA 2024). As an added bonus, we show that semi-sample-based testers also exist for the lifted affine-invariant codes of Guo, Kopparty, and Sudan (ITCS 2013), thereby providing the first known testers for these codes in the online-erasure model.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper defines semi-sample-based testers for Reed-Muller codes in the online-erasure model: the tester first selects a fixed subset S of the domain and then issues queries chosen uniformly at random inside S. It provides an optimal soundness analysis showing that these testers achieve constant detection probability against an adversary that erases up to t points after each query, thereby attaining optimal query complexity. The result improves on Minzer and Zheng (SODA 2024) and is extended to lifted affine-invariant codes of Guo, Kopparty, and Sudan.

Significance. If the soundness analysis holds, the work establishes the first optimal testers for Reed-Muller codes under online erasures, a model motivated by recent property-testing applications. The hybrid semi-sample-based approach is a clean conceptual contribution that bridges sample-based and adaptive testers while remaining robust to adaptive erasures. The extension to lifted codes is a useful bonus. The paper supplies a fresh, parameter-free-style analysis of the hybrid tester rather than relying on prior self-citations.

major comments (1)
  1. [Soundness analysis (likely §4 or §5)] The central claim (abstract and §1) is that the soundness analysis of the semi-sample-based tester continues to guarantee constant detection probability when the input is far from the RM code. However, the initial S is chosen without knowledge of future erasures, and the adversary can erase up to t points after each of the q queries. The analysis must therefore bound the worst-case erosion of |S| by t·q points and show that the induced distribution over the remaining points still preserves the required distance-to-code lower bound. Please identify the specific lemma or theorem that handles this adaptive thinning and state the quantitative bound on the detection probability.
minor comments (1)
  1. [Abstract] The abstract states that the testers 'achieve optimal query complexity' but does not explicitly restate the precise bound (in terms of n, degree, and t) achieved; adding this sentence would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for their positive assessment of the conceptual contribution of semi-sample-based testers. We address the major comment below.

read point-by-point responses

  1. Referee: [Soundness analysis (likely §4 or §5)] The central claim (abstract and §1) is that the soundness analysis of the semi-sample-based tester continues to guarantee constant detection probability when the input is far from the RM code. However, the initial S is chosen without knowledge of future erasures, and the adversary can erase up to t points after each of the q queries. The analysis must therefore bound the worst-case erosion of |S| by t·q points and show that the induced distribution over the remaining points still preserves the required distance-to-code lower bound. Please identify the specific lemma or theorem that handles this adaptive thinning and state the quantitative bound on the detection probability.

    Authors: The adaptive thinning due to online erasures is handled explicitly in the proof of Theorem 5.1 (Section 5), which establishes that the semi-sample-based tester detects inputs that are δ-far from the Reed-Muller code with probability at least 1/100. The argument first fixes the set S of size Θ(1/ε²) (chosen independently of the adversary), then considers an arbitrary sequence of at most t erasures after each of the q queries. Lemma 5.3 shows that at most t·q points are removed from S in the worst case, so the surviving set S' satisfies |S'| ≥ |S| − t·q. Because queries are drawn uniformly from the original S, the induced distribution on S' remains sufficiently close to uniform; combined with the distance-to-code lower bound for Reed-Muller codes, this yields a detection probability that is at least a constant factor smaller than the non-erasure case but still bounded below by the absolute constant 1/100 for all sufficiently large n. We will add an explicit forward pointer from the introduction and abstract to Theorem 5.1 and Lemma 5.3 to make this quantitative guarantee easier to locate. revision: partial

Circularity Check

0 steps flagged

No significant circularity; soundness analysis is a direct, independent argument

full rationale

The paper defines semi-sample-based testers explicitly as first selecting a fixed subset S of the domain and then querying uniformly at random inside S. It then supplies a fresh soundness analysis showing that this hybrid tester retains constant detection probability against an online adversary that erases up to t points after each query. The optimality claim follows directly from combining this analysis with known query-complexity lower bounds for Reed-Muller testing; neither step reduces to a fitted parameter, a self-referential definition, or a load-bearing self-citation whose validity is presupposed inside the present work. The citation to Minzer and Zheng (SODA 2024) is used only for context and improvement, not as the sole justification for the central soundness result.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on standard finite-field and coding-theory background; no free parameters or new invented entities are introduced in the abstract.

axioms (1)
  • standard math Standard algebraic properties of Reed-Muller codes over finite fields
    Invoked when defining the code and distance notions used in the testing task.

pith-pipeline@v0.9.0 · 5887 in / 1155 out tokens · 40187 ms · 2026-05-22T02:50:58.422346+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages · 1 internal anchor

  1. [1]

    On optimal testing of linearity

    [AKM25] Vipul Arora, Esty Kelman, and Uri Meir. On optimal testing of linearity. In Ioana Ori- ana Bercea and Rasmus Pagh, editors,2025 Symposium on Simplicity in Algorithms, SOSA 2025, New Orleans, LA, USA, January 13-15, 2025, pages 65–76. SIAM,

    work page 2025

  2. [2]

    Probabilistic checking of proofs; A new characteri- zation of NP

    34 [AS92] Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs; A new characteri- zation of NP. In33rd Annual Symposium on Foundations of Computer Science, Pitts- burgh, Pennsylvania, USA, October 24-27, 1992, pages 2–13. IEEE Computer Society,

    work page 1992

  3. [3]

    [BDN16] Amey Bhangale, Irit Dinur, and Inbal Livni Navon. Cube vs. cube low degree test. CoRR, abs/1612.07491,

    work page internal anchor Pith review Pith/arXiv arXiv

  4. [4]

    Every locally characterized affine-invariant property is testable

    [BFH+13] Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, and Shachar Lovett. Every locally characterized affine-invariant property is testable. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors,Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 429–436. ACM,

    work page 2013

  5. [5]

    Testing low complexity affine-invariant properties

    [BFL13] Arnab Bhattacharyya, Eldar Fischer, and Shachar Lovett. Testing low complexity affine-invariant properties. In Sanjeev Khanna, editor,Proceedings of the Twenty- Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Or- leans, Louisiana, USA, January 6-8, 2013, pages 1337–1355. SIAM,

    work page 2013

  6. [6]

    Property testing with online adversaries

    [BKMR24] Omri Ben-Eliezer, Esty Kelman, Uri Meir, and Sofya Raskhodnikova. Property testing with online adversaries. In15th Innovations in Theoretical Computer Science Confer- ence (ITCS 2024). Schloss-Dagstuhl-Leibniz Zentrum f¨ ur Informatik,

    work page 2024

  7. [7]

    New affine-invariant codes from lifting

    [GKS13] Alan Guo, Swastik Kopparty, and Madhu Sudan. New affine-invariant codes from lifting. In Robert D. Kleinberg, editor,Innovations in Theoretical Computer Science, ITCS ’13, Berkeley, CA, USA, January 9-12, 2013, pages 529–540. ACM,

    work page 2013

  8. [8]

    An improved line-point low-degree test

    35 [HKSS24] Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, and Madhu Sudan. An improved line-point low-degree test. In65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024, pages 1883–1892. IEEE,

    work page 2024

  9. [9]

    Online versus offline ad- versaries in property testing

    [KLR25] Esty Kelman, Ephraim Linder, and Sofya Raskhodnikova. Online versus offline ad- versaries in property testing. In Raghu Meka, editor,16th Innovations in Theoretical Computer Science Conference, ITCS 2025, January 7-10, 2025, Columbia University, New York, NY, USA, volume 325 ofLIPIcs, pages 65:1–65:18. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik,

    work page 2025

  10. [10]

    Homomorphism testing with resilience to online manipulations.arXiv preprint arXiv:2511.23363,

    [KMNR25] Esty Kelman, Uri Meir, Debanuj Nayak, and Sofya Raskhodnikova. Homomorphism testing with resilience to online manipulations.arXiv preprint arXiv:2511.23363,

    work page arXiv

  11. [11]

    Approaching the soundness barrier: A near optimal analysis of the cube versus cube test

    [MZ23a] Dor Minzer and Kai Zheng. Approaching the soundness barrier: A near optimal analysis of the cube versus cube test. 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 2761–2776. SIAM,

    work page 2023

  12. [12]

    Optimal testing of generalized reed-muller codes in fewer queries

    [MZ23b] Dor Minzer and Kai Zhe Zheng. Optimal testing of generalized reed-muller codes in fewer queries. In64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 206–233. IEEE,

    work page 2023

  13. [13]

    Adversarial low degree testing

    36 [MZ24a] 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,

    work page 2024

  14. [14]

    Near optimal alphabet-soundness tradeoff pcps

    [MZ24b] Dor Minzer and Kai Zhe Zheng. Near optimal alphabet-soundness tradeoff pcps. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors,Proceedings of the 56th An- nual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 15–23. ACM,

    work page 2024

  15. [15]

    A sub-constant error-probability low-degree test, and a sub- constant error-probability PCP characterization of NP

    [RS97] Ran Raz and Shmuel Safra. A sub-constant error-probability low-degree test, and a sub- constant error-probability PCP characterization of NP. In Frank Thomson Leighton and Peter W. Shor, editors,Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997, pages 475–484. ACM,

    work page 1997

  16. [16]

    New direct sum tests.CoRR, abs/2409.10464,

    [WYZ24] Alek Westover, Edward Yu, and Kai Zheng. New direct sum tests.CoRR, abs/2409.10464,

    work page arXiv