K. Zheng

most citedImproved Round-by-round Soundness IOPs via Reed-Muller Codes

1 citations · 1 across the 1 of their papers we have counts for

collaborators

3 papers

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★ 1 cited

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…

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