Kai Zhe Zheng
Hello! I am a fourth year PhD student in Mathematics at MIT, where I am fortunate to be advised by Dor Minzer. I am interested in complexity theory, PCPs, and error correcting codes.
If you are interested in any of my work feel free to reach out! kzzheng[at]mit.edu
Publications:
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).