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.

We construct $3$-query relaxed locally decodable codes (RLDCs) with constant alphabet size and length $\tilde{O}(k^2)$ for $k$-bit messages. Combined with the lower bound of $\tildeΩ(k^3)$ of [Alrabiah, Guruswami, Kothari, Manohar, STOC 2023] on the length of locally decodable codes (LDCs) with the same parameters, we obtain a separation between RLDCs and LDCs, resolving an open problem of [Ben-Sasson, Goldreich, Harsha, Sudan and Vadhan, SICOMP 2006]. Our RLDC construction relies on two components. First, we give a new construction of probabilistically checkable proofs of proximity (PCPPs) with $3$ queries, quasi-linear size, constant alphabet size, perfect completeness, and small soundness error. This improves upon all previous PCPP constructions, which either had a much higher query complexity or soundness close to $1$. Second, we give a query-preserving transformation from PCPPs to RLDCs. At the heart of our PCPP construction is a $2$-query decodable PCP (dPCP) with matching parameters, and our construction builds on the HDX-based PCP of [Bafna, Minzer, Vyas, Yun, STOC 2025] and on the efficient composition framework of [Moshkovitz, Raz, JACM 2010] and [Dinur, Harsha, SICOMP 2013]. More specifically, we first show how to use the HDX-based construction to get a dPCP with matching parameters but a large alphabet size, and then prove an appropriate composition theorem (and related transformations) to reduce the alphabet size in dPCPs.

We show that for every k∈ℕ and ε>0, for large enough alphabet R, given a k-CSP with alphabet size R, it is NP-hard to distinguish between the case that there is an assignment satisfying at least 1−ε fraction of the constraints, and the case no assignment satisfies more than 1/Rk−1−ε of the constraints. This result improves upon prior work of [Chan, Journal of the ACM 2016], who showed the same result with weaker soundness of O(k/Rk−2), and nearly matches the trivial approximation algorithm that finds an assignment satisfying at least 1/Rk−1 fraction of the constraints. Our proof follows the approach of a recent work [Minzer and Zheng, STOC 2024] of the authors, wherein the above result is proved for k=2. Our main new ingredient is a counting lemma for hyperedges between pseudo-random sets in the Grassmann graphs, which may be of independent interest.

We give an IOPP (interactive oracle proof of proximity) for trivariate Reed-Muller codes that achieves the best known query complexity in some range of security parameters. Specifically, for degree d and security parameter $\lambda \leq \frac{\log ^{2} d}{\log \log d}$, our IOPP has $2^{-\lambda}$ round-byround soundness, $O(\lambda)$ queries, $O(\log \log d)$ rounds and $O(d)$ length. This improves upon the FRI [Ben-Sasson, Bentov, Horesh, Riabzev, ICALP 2018] and the STIR [Arnon, Chiesa, Fenzi, Yogev, Crypto 2024] IOPPs for Reed-Solomon codes, that have larger query and round complexity standing at $O(\lambda \log d)$ and $O(\log d+\lambda \log \log d)$ respectively. We use our IOPP to give an IOP for the NPcomplete language R1CS with the same parameters. Our construction is based on the line versus point test in the low-soundness regime. Compared to the axis parallel test (which is used in all prior works), the general affine lines test has improved soundness, which is the main source of our improved soundness. Using this test involves several complications, most significantly that projection to affine lines does not preserve individual degrees, and we show how to overcome these difficulties. En route, we extend some existing machinery to more general settings. Specifically, we give proximity generators for Reed-Muller codes, show a more systematic way of handling “side conditions” in IOP constructions, and generalize the compiling procedure of [Arnon, Chiesa, Fenzi, Yogev, Crypto 2024] to general codes.

In the t-online-erasure model in property testing, an adversary is allowed to erase t values of a queried function for each query the tester makes. This model was recently formulated by Kalemaj, Raskhodnikova and Varma, who showed that the properties of linearity of functions as well as quadraticity can be tested in Ot (1) many queries: O(log(t)) for linearity and 22O(t) for quadraticity. They asked whether the more general property of low-degreeness can be tested in the online erasure model, whether better testers exist for quadraticity, and if similar results hold when “erasures” are replaced with “corruptions”.

We show that for all є>0, for sufficiently large prime power q, for all δ>0, it is NP-hard to distinguish whether a 2-Prover-1-Round projection game with alphabet size q has value at least 1-δ, or value at most 1/q^(1-є). This establishes a nearly optimal alphabet-to-soundness tradeoff for 2-query PCPs with alphabet size q, improving upon a result of [Chan 2016]. Our result has the following implications:

A local tester for an error correcting code $C\subseteq\Sigma^{n}$ is a tester that makes Q oracle queries to a given word $w\in\bar{\Sigma}^{n}$ and decides to accept or reject the word w. An optimal local tester is a local tester that has the additional properties of completeness and optimal soundness. By completeness, we mean that the tester must accept with probability 1 if $w\in C$. By optimal soundness, we mean that if the tester accepts with probability at least $ 1-\varepsilon$ (where $\varepsilon$ is small), then it must be the case that w is $O(\varepsilon/Q)$-close to some codeword $c\in C$ in Hamming distance. We show that Generalized Reed-Muller codes admit optimal testers with $Q=(C_{p}q)^{\lceil\frac{d+1}{q-1}\rceil+O(1)}$ queries for $C_{p}=(2p-1)^{\frac{1}{p-1}}$. Here, for a prime power $q=p^{k}$, the Generalized Reed-Muller code, $\operatorname{RM}[n, q, d]$, consists of the evaluations of all n-variate degree d polynomials over $\mathbb{F}_{q}$. As $p,q$, and d go to infinity, Q matches the known lower bound of $q^{\frac{d+1}{q-1}}$ up to a multiplicative factor of 1. Previously, no tester achieving this query complexity was known, and the best known testers due to Haramaty, Shpilka and Sudan [21] (which is optimal) and due to Ron-Zewi and Sudan [33](which was not known to be optimal) both required $q^{\lceil\frac{d+1}{q-q/p}\rceil}$ queries. Our tester achieves query complexity which is polynomially better than by a power of $p/(p-1)$, which is nearly the best query complexity possible for generalized Reed-Muller codes. The tester we analyze is constructed using the same framework of Ron-Zewi and Sudan, and in fact our analysis shows that their tester is optimal as well. More generally, our methods allow us to prove that a wide class of testers, which follow the form of the Ron-Zewi and Sudan tester, are optimal. This result applies to testers for all affine-invariant codes (which are not necessarily generalized Reed-Muller codes).