Kai Zhe Zheng

Hello! I am a fifth year PhD student in Mathematics at MIT, where I am fortunate to be advised by Dor Minzer. I am interested in complexity theory, PCPs, Proof Systems, and combinatorics.

Previously, I received an A.B. in Mathematics at Princeton University. As an undergraduate I had the privilege of working with Noga Alon and Robert Tarjan, as well as Joe Gallian and Colin Defant at the Duluth REU.

If you are interested in any of my work feel free to reach out! kzzheng[at]mit.edu

Publications:

Near Optimal Hardness of Approximating k-CSP,

with Dor Minzer, [arxiv],

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

with Dor Minzer, [arxiv].

(FOCS 2025).

New Direct Sum Tests,

with Alek Westover and Edward Yu, [arxiv],

(ITCS 2025). [Hartley Rogers Jr. Prize @ MIT]

Near Optimal Alphabet-Soundness Tradeoff PCPs,

with Dor Minzer, [ECCC],

(STOC 2024). [STOC Best Paper Award], [Charles W. and Jennifer C. Johnson Prize @ MIT]

Adversarial Low Degree Testing,

with Dor Minzer, [arxiv],

(SODA 2024).

Optimal Testing of Generalized Reed-Muller Codes in Fewer Queries,

with Dor Minzer, [arxiv],

(FOCS 2023).

Approaching the Soundness Barrier: A Near Optimal Analysis of the Cube versus Cube Test,

with Dor Minzer, [arxiv],

(SODA 2023).

On the e-positivity of trees and spiders, [arxiv],

(Journal of Combinatorial Theory, Series A).

Stack-Sorting with Consecutive-Pattern-Avoiding Stacks,

with Colin Defant, [arxiv],

(Advances in Applied Mathematics).

Unitary Signings and Induced Subgraphs of Cayley Graphs of (ℤ_2)^n,

with Noga Alon, [arxiv],

(Advances in Combinatorics).

Page updated

Google Sites

Report abuse