DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2026.31

Optimal Testing of Reed-Muller Codes with an Online Adversary

Authors: Esty Kelman, Uri Meir, and Kai Zhe Zheng

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

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 semi-sample-based testers for Reed-Muller codes. The task in Reed-Muller testing is to determine whether an input function 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.

Cite as

Esty Kelman, Uri Meir, and Kai Zhe Zheng. Optimal Testing of Reed-Muller Codes with an Online Adversary. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 31:1-31:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kelman_et_al:LIPIcs.CCC.2026.31,
  author =	{Kelman, Esty and Meir, Uri and Zheng, Kai Zhe},
  title =	{{Optimal Testing of Reed-Muller Codes with an Online Adversary}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{31:1--31:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.31},
  URN =		{urn:nbn:de:0030-drops-270732},
  doi =		{10.4230/LIPIcs.CCC.2026.31},
  annote =	{Keywords: Property testing, Low degree testing}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2025.94

New Direct Sum Tests

Authors: Alek Westover, Edward Yu, and Kai Zhe Zheng

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract

A function f:[n]^{d} → 𝔽₂ is a direct sum if there are functions L_i:[n] → 𝔽₂ such that f(x) = ∑_i L_i(x_i). In this work we give multiple results related to the property testing of direct sums. Our first result concerns a test proposed by Dinur and Golubev in [Dinur and Golubev, 2019]. We call their test the Diamond test and show that it is indeed a direct sum tester. More specifically, we show that if a function f is ε-far from being a direct sum function, then the Diamond test rejects f with probability at least Ω_{n,ε}(1). Even in the case of n = 2, the Diamond test is, to the best of our knowledge, novel and yields a new tester for the classic property of affinity. Apart from the Diamond test, we also analyze a broad family of direct sum tests, which at a high level, run an arbitrary affinity test on the restriction of f to a random hypercube inside of [n]^d. This family of tests includes the direct sum test analyzed in [Dinur and Golubev, 2019], but does not include the Diamond test. As an application of our result, we obtain a direct sum test which works in the online adversary model of [Iden Kalemaj et al., 2022]. Finally, we also discuss a Fourier analytic interpretation of the diamond tester in the n = 2 case, as well as prove local correction results for direct sum as conjectured by [Dinur and Golubev, 2019].

Cite as

Alek Westover, Edward Yu, and Kai Zhe Zheng. New Direct Sum Tests. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 94:1-94:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{westover_et_al:LIPIcs.ITCS.2025.94,
  author =	{Westover, Alek and Yu, Edward and Zheng, Kai Zhe},
  title =	{{New Direct Sum Tests}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{94:1--94:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.94},
  URN =		{urn:nbn:de:0030-drops-227229},
  doi =		{10.4230/LIPIcs.ITCS.2025.94},
  annote =	{Keywords: Linearity testing, Direct sum, Grids}
}

Search Results

Documents authored by Zheng, Kai Zhe

Optimal Testing of Reed-Muller Codes with an Online Adversary

Abstract

Cite as

New Direct Sum Tests

Abstract

Cite as

Thanks for your feedback!

Could not send message