Date: November 24, 2025

Time: 3:45-5 p.m.

Location: Gates Hall 310 or via Zoom

Speaker: Kai Zhe Zheng

Title: Reed-Muller based IOPs via the Line vs. Point Test 




Abstract: 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 -- improving upon the FRI [Ben-Sasson, Bentov, Horesh, Riabzev, ICALP 2018] and the STIR [Arnon, Chiesa, Fenzi, Yogev, Crypto 2024] IOPPs for Reed-Solomon codes. We use our IOPP to give an IOP for the NP-complete language Rank-1-Constraint-Satisfaction with the same parameters. Our IOPP also extends to an inverse polynomial soundness IOP for NP with parameters matching a recent work by [Arnon, Chiesa, Yogev, FOCS 2023]. 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.

Based on Joint work with Dor Minzer.

Bio: Kai is a Ph.D. Student in the MIT Mathematics Department advised by Dor Minzer. His research focuses on probabilistic proof systems and their applications in complexity theory and cryptography. He is a recipient of a STOC Best paper award, the MIT Presidential Fellowship, and the Johnson Prize from the MIT Mathematics Department.