Amik Raj Behera

All known proofs of the PCP Theorem (polynomial-sized proof with constant query) are via compositions of different PCPs one after another, and the number of compositions is at least 2.

We give the first proof of the PCP Theorem with a single composition step. Moreover, our two PCPs are just different instantiations of a generic PCP that we construct.

The key contribution of our work is to give an efficient test to check whether a multivariate low-degree polynomial vanishes on a subset S of the domain. These tests can be interpreted as alternatives to the usual sumcheck protocol.

[ECCC] [arXiv]

We consider random walks on the balanced multislice of {0,1,...,s}^{n}, i.e., the set of points with equal number of 0's, equal number of 1's, and so on. We say a random walk respects symmetries if the transition probability remains the same when the coordinates of the initial and final states are permuted simultaneously.

We show that random walks on balanced multislices that respect symmetries and satisfy a couple of other properties have good spectral expansion.

As applications, 

• We give a polynomial distance lemma over balanced multislices

• Local (list) correction algorithms for variants of Reed-Muller codes. 

[RANDOM 2025] [ECCC] [arXiv] [doi]

[Slides of a talk by Madhu] [Slides of a talk by Prashanth] [Slides of a survey talk by Madhu]

A classical result on low-degree polynomials shows that every non-zero degree-d polynomial over the Boolean cube is non-zero on at least 1/2^{d} fraction of points. In this work, we consider the following generalization:

Given a degree-d non-zero polynomial (in n variables) over any Boolean slice, on how many points is it non-zero over that slice?

 The  k^{th} slice refers to the set of all Boolean points of Hamming weight exactly k.

We show that the answer is nearly  (k/n)^{d}. In particular, for the middle slice (k = n/2), our bound is nearly 1/2^{d}.

[ICALP 2025] [ECCC] [arXiv] [doi]

[Slides of a talk by Amik]

Ideal Proof System is an algebraic proof system,  where Hilbert's Nullstellensatz gives the refutations, and the complexity is measured in terms of the algebraic complexity of the certificate. Motivated by proof complexity, we are typically interested in understanding whether a model of computation can refute a system of polynomials. In this work, we consider IPS over fields of positive characteristic.

We prove lower bounds for various restricted models of computation, such as multilinear constant-depth algebraic circuits, roABPs, and more.

We also prove upper bounds for restricted systems of polynomials:

• A sparse polynomial.

• A system of symmetric polynomials.

[ICALP 2025] [ECCC] [arXiv] [doi]

[Slides of a talk by Amik]

A constrained PRF is a PRF that has a constrained key that allows evaluations on a specific subset of the domain. Such PRFs are private if the constrained key returns no information about the subset.

In this work, we look at private constrained PRFs where the PRF evaluates everywhere except a fixed point in the domain. This is known as private punctured PRFs. Previous constructions either used assumptions such as LWE/IO or supported only polynomial-sized domains.

We construct private punctured PRFs using group assumptions (in particular, the Decisional Composite Residuosity assumption) that support exponential-sized domains.

[TCC 2025] [ePrint]

In the problem of local correction, we are given a function promised to be close to a unique low-degree polynomial, and the task is to recover local information of the low-degree polynomial by making queries to the input function. We consider low-degree polynomials with Boolean cube as the domain and coefficients are real numbers.

We give a sublinear query local corrector algorithm.

We also consider the problem of local list correction, we are given a function, which is close to several low-degree polynomials. The task is to recover local information of all the close low-degree polynomials by making queries to the input function (the setup is the same as local correction).

We show that the number of close linear functions is small (a combinatorial bound) and give a local list corrector algorithm.

This work extends the results of [ABPSS'24], who considered these problems for linear functions. 

[SODA 2025] [ECCC] [arXiv] [doi]

[Talk by Prashanth] [Slides of a talk by Amik] [Slides of a talk by Prashanth]

In the problem of local correction, we are given a polynomial promised to be close to a unique linear function, and the task is to recover local information of the linear function by making queries to the input polynomial. We consider linear functions with Boolean cube as the domain and coefficients are real numbers.

We give a nearly optimal local corrector algorithm (in terms of queries).

We also consider the problem of local list correction, we are given a polynomial, which is close to several linear functions. The task is to recover local information of all the close linear functions by making queries to the input polynomial (the setup is the same as local correction).

We show that the number of close linear functions is small (a combinatorial bound) and give a local list corrector algorithm.

[STOC 2024] [ECCC] [arXiv] [doi]

[Talk by Madhu] [Slides of a talk by Amik] [STOC Recorded Video] [Slides of a talk by Prashanth]