1 citations · 1 across the 5 of their papers we have counts for
7 papers
Optimal Testing of Reed-Muller Codes with an Online Adversary
Esty Kelman, Uri Meir, Kai Zhe Zheng
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…
3-Query RLDCs are Strictly Stronger than 3-Query LDCs
Tom Gur, Dor Minzer, Guy Weissenberg +1
We construct -query relaxed locally decodable codes (RLDCs) with constant alphabet size and length for -bit messages. Combined with the lower bound of $\tild…
Near Optimal Hardness of Approximating -CSP
Dor Minzer, Kai Zhe Zheng
We show that for every and , for large enough alphabet , given a -CSP with alphabet size , it is NP-hard to distinguish between the case th…
Improved Round-by-round Soundness IOPs via Reed-Muller Codes
Dor Minzer, Kai Zhe Zheng
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. Specifi…
Near Optimal Alphabet-Soundness Tradeoff PCPs
Dor Minzer, Kai Zhe Zheng
We show that for all , for sufficiently large power of , for all , it is NP-hard to distinguish whether a given -Prover--Round project…
Adversarial Low Degree Testing
Dor Minzer, Kai Zhe Zheng
In the -online-erasure model in property testing, an adversary is allowed to erase values of a queried function for each query the tester makes. This model was recently form…
Optimal Testing of Generalized Reed-Muller Codes in Fewer Queries
Dor Minzer, Kai Zheng
A local tester for an error correcting code is a tester that makes oracle queries to a given word and decides to accept or reject the word . An…