Amik Raj Behera

Low-degree testing is an algorithm that queries a function and decides whether it is a low-degree polynomial (on the domain of the function) or far from every low-degree polynomial. Due to its applications in PCPs, IPs, and other related areas, this problem has been studied quite extensively. The usual setting is that the domain is a vector space, and the range is a finite field. Some works also studied when the domain is more combinatorial, such as the Boolean hypercube and Boolean slices.

In this work, we give a low-degree testing algorithm when the domain is Boolean slices and the range is an arbitrary field (even fields of characteristic 0). The query complexity of our algorithm only depends on the degree parameter and is independent of the number of dimensions.

The key idea is to reduce testing over Boolean slices to testing over Boolean hypercubes. We also use a specific basis of degree-d polynomials over Boolean slices that allows us to define a "global polynomial" and argue that it is degree-d.

[ECCC] [arXiv]

Known algebraic proofs of the PCP Theorem (polynomial-sized proof with constant queries) proceed by first constructing different "atomic PCPs" and then combining them together using the technique of proof composition. Proof composition is an extension of code concatenation (this is a simple process of combining two codes together to get a code with better parameters) but involves more steps, such as going through an NP-completeness reduction.

We give a new proof of the PCP Theorem via code concatenation and do not use any NP-completeness reduction. 

We first abstract out that the bottleneck lies in the low-degree test. To handle this, we come up with an encoding of large-degree univariate polynomials to constant-degree multivariate polynomials (it is a set-multilinear version of the inverse Kronecker substitution). Then we concatenate it with a low-degree Hadamard code.

[ECCC] [arXiv]

Sophus created a demo of our PCP prover and verifier with the help of AI. Check it out here.

It is known that an exp(omega(d^{1/3} log n)) lower bound for depth-4 circuits whose top product gate has fan-in at most exp(O(d^{1/3} log d)), over characteristic 0, implies VP is not equal to VNP.

In this work, we consider small finite fields. Here, an exp(Omega(d^{1/2})) lower bound for depth-4 circuits whose top product gate has fan-in at most O(d^{1/2}).

We improve the parameters of the above work and prove an exp(Omega(d^{1/2})) lower bound for depth-4 circuits whose top product gate has fan-in at most poly(d), over small finite fields. We use a 'functional' variant of the shifted partial derivatives as complexity measure.

[ECCC]

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.

We prove a hierarchy amongst constant-depth IPS over fields of characteristic 0. We also prove a separation between a restriction of a multilinear formula IPS and the class multilinear-circuit IPS.

To prove our results, we show how to modify an algebraic circuit using gadgets such that every gate takes a value in a small set when the inputs are restricted to the Boolean cube.

[ECCC] [arXiv]

All known proofs of the PCP Theorem (polynomial-sized proof with constant queries) 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.

[To appear in STOC 2026] [ECCC] [arXiv] [doi]

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

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] [Slides of another talk by Amik (with technical details)]

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]