A Probabilistically Checkable Proof (PCPs) is a proof system with a probabilistic verifier that queries the given proof and either accepts or rejects. One would like to minimize the number of random bits and the number of queries made by the verifier. PCPs are a generalization of the complexity class NP. In fact, a celebrated result of Arora, Lund, Motwani, Sudan, Szegedy characterized NP by a PCP with O(log n) randomness and constant queries, which is known as the PCP Theorem.
In this work, we give a new and a simpler proof of the PCP Theorem by constructing a class of PCPs with range of parameters which was not known before. To achieve this, we introduce "Zero-on-Variety Test", which acts as an alternative to sum-check protocols. Finally, to get a PCP of our choice of parameters, we apply the Zero-on-Variety test on subsets related to Boolean slices. Our new protocols build on ideas from the theory of Gröbner bases.
This is based on a joint work with Prashanth Amireddy, Srikanth Srinivasan, Madhu Sudan, and Sophus Valentin Willumsgaard, and can be found here: https://eccc.weizmann.ac.il/report/2025/165/
Short Bio : Amik Raj Behera is a Ph.D. student at the University of Copenhagen under the guidance of Prof. Srikanth Srinivasan. He did his master's at Aarhus University and bachelor's at the Chennai Mathematical Institute. His research interests are in complexity theory, coding theory, and problems with an algebraic flavor.
