K. Zheng

collaborators

5 papers

cs.DS2026

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…

cs.CC2026

Near Optimal Alphabet-Soundness Tradeoff PCPs

Dor Minzer, Kai Zhe Zheng

We show that for all $ε > 0$ , for sufficiently large $q \in N$ power of $2$ , for all $I^´ > 0$ , it is NP-hard to distinguish whether a given $2$ -Prover- $1$ -Round projec…

cs.CC2025

3-Query RLDCs are Strictly Stronger than 3-Query LDCs

Tom Gur, Dor Minzer, Guy Weissenberg +1

We construct $3$ -query relaxed locally decodable codes (RLDCs) with constant alphabet size and length $O ~ (k^{2})$ for $k$ -bit messages. Combined with the lower bound of $\tild…

cs.CC2025

Near Optimal Hardness of Approximating $k$ -CSP

Dor Minzer, Kai Zhe Zheng

We show that for every $k \in N$ and $ε > 0$ , for large enough alphabet $R$ , given a $k$ -CSP with alphabet size $R$ , it is NP-hard to distinguish between the case th…

cs.CC2025

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…

Optimal Testing of Reed-Muller Codes with an Online Adversary

Near Optimal Alphabet-Soundness Tradeoff PCPs

3-Query RLDCs are Strictly Stronger than 3-Query LDCs

Near Optimal Hardness of Approximating k-CSP

Improved Round-by-round Soundness IOPs via Reed-Muller Codes

Near Optimal Hardness of Approximating $k$ -CSP