Optimal Testing of Reed-Muller Codes with an Online Adversary

Esty Kelman, Uri Meir, Kai Zhe Zheng · 2026

Read Optimal Testing of Reed-Muller Codes with an Online Adversary by Esty Kelman, Uri Meir, Kai Zhe Zheng (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-22813.txt.

Introduction

Kelman, Meir, and Zheng study testing Reed-Muller codes under an online adversary. The task is to tell whether a function lies in the code or far from it. After each query, the adversary may erase points of the input. The authors define semi-sample-based testers, which choose a subset of the domain and query inside it at random. They prove optimal soundness for these testers. This yields optimal query complexity under online erasures, and the testers extend to lifted affine-invariant codes.

Catalog record

CREATOREsty Kelman, Uri Meir, Kai Zhe Zheng
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE110163
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.22813

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Optimal Testing of Reed-Muller Codes with an Online Adversary Esty Kelman, Uri Meir, Kai Zhe Zheng 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 : 𝔽 n → 𝔽 f:\mathbb{F}^{n}\to\mathbb{F} belongs to the Reed-Muller code or is far from it, using as few point queries to f 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 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 S of the domain and then making their queries uniformly at random inside of S 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. 1 Introduction Local testing of the Reed-Muller code is a fundamental problem in property testing and complexity theory. In this problem, we are given oracle access to a multivariate function over a finite field, f:\mathbb{F}^{n}\to\mathbb{F} , and must decide whether f is a polynomial of total degree at most d , or is instead far from every polynomial of degree at most d . The notion of distance used here is the fractional Hamming distance. The goal is to design a randomized algorithm, called a tester , that accepts f with probability 1 in the former case and rejects f with probability at least 2/3 in the latter case, while making as few queries to f as possible. Ideally, the query complexity should be independent of n . The problem of Reed-Muller testing has been extensively explored over the past few decades. Its study began with the degree- 1 case, which was considered in the seminal work of Blum, Luby, and Rubinfeld [ BLR93 ] . Their work introduced the well-known BLR linearity test and, more broadly, initiated the field of property testing. Subsequently, a large body of work gave and optimized testers for the general degree d case, d>1 [ AKK+05 , KR06 , BKS+10 , HSS13 , RZS13 , KM25 , MZ23b ] . Additionally, a related variant of the Reed-Muller testing problem was instrumental in the early construction of Probabilistically Checkable Proofs (PCPs) [ AS92 , RS97 ] , and has continued to inspire subsequent research, including [ MR08 , BDN16 , MZ23a , HKSS24 , BR25 ] . More recently, a new model of property testing introduced by Kalemaj, Raskhodnikova, and Varma, called the online-erasure model [ KRV23 ] , has garnered significant attention. Several works have revisited Reed-Muller testing and related questions in this setting [ KRV23 , MZ24a , BKMR24 , WYZ24 , AKM25 , KLR25 , KMNR25 ] . In this model, an adversary may erase up to t inputs after each query f(x) is made, where typically t is assumed to be small relative to the domain size |\mathbb{F}|^{n} . Testers that work in the online-erasure model are called online-erasure-resilient . We continue this line of work and give improved online-erasure-resilient testers for the Reed-Muller code. Our testers have query complexity that improves upon the previous state of the art in [ MZ24a ] . In addition, we give a matching lower bound showing that, for fixed field size and degree parameter, our query complexity is optimal as a function of the erasure rate parameter t . Toward this result, we find it convenient to define a new class of testers, which we refer to as semi-sample-based testers . At a high level, semi-sample-based testers make their queries uniformly at random within some moderately large set of points S . In the case of Reed-Muller testing, the set S\subset\mathbb{F}^{n} is chosen to have size independent of n , but still sufficiently large as a function of t , d , and q:=|\mathbb{F}| . By making S large enough relative to the number of queries made, we ensure that our semi-sample-based testers are also online-erasure-resilient. Beyond Reed-Muller codes, we note that our approach extends naturally to give semi-sample-based testers for the lifted affine-invariant codes of [ GKS13 ] . To the best of our knowledge, these are the first testers for these codes that are resilient to online erasures. We believe that the notion of semi-sample-based testing is conceptually useful and may find further applications in property testing, particularly in adversarial models such as the online-erasure model. To motivate this notion and explain why it arises naturally in this setting, we examine several natural candidate testers for Reed-Muller codes and show why they fail under online erasures. These candidates represent two extremes, which semi-sample-based testers naturally interpolate between. For simplicity, we restrict the discussion below to the case d=1 , as these issues already arise in this setting. The Standard Tester. A first approach one might try is to run the standard tester in the online-erasure model. This tester is the well-known BLR linearity tester, which chooses x,y\in\mathbb{F}^{n} uniformly at random, queries f(x) , f(y) , and f(x+y) , and then checks whether f(x)+f(y)=f(x+y) . While this tester has optimal query complexity in the standard model, it fails completely in the online-erasure model. Indeed, an adversary can erase the value f(x+y) after the first two queries are made, making it impossible to carry out the test. The issue here is that the queries are too structured . Sample-based testing. At the other extreme, one can design a tester whose queries are as unstructured as possible. For example, one may consider a tester that queries f at uniformly random points x\in\mathbb{F}^{n} . Such testers were introduced in [ GGR98 ] and are called sample-based testers . In this case, it is unlikely that an erased point is ever queried (since t\ll|\mathbb{F}|^{n} ), but this robustness comes at a cost: the tester requires at least n queries to succeed. Indeed, as shown in [ GR16 ] , with high probability, any set of fewer than n uniformly random points is linearly independent, and therefore there always exists a linear function that agrees with f on those points. Thus, while sample-based testers are robust to online erasures, they are not query efficient. Semi-sample-based testing. Semi-sample-based testers interpolate between these two extremes. They operate by first choosing a

Read the complete text