9 papers · 1 filter
Low-Degree Testing Over Boolean Slices
Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan +2
We study low-degree testing for group-valued functions over a Boolean slice. Specifically given a degree parameter and oracle access to a function wher…
A Simple Algebraic Proof of the PCP Theorem
Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan +2
We give the simplest known algebraic proof of the PCP theorem, involving only ingredients like code concatenation, polynomial interpolation, and polynomial multiplication. Specific…
Separation Results for Constant-Depth and Multilinear Ideal Proof Systems
Amik Raj Behera, Magnus Rahbek Dalgaard Hansen, Nutan Limaye +1
In this work, we establish separation theorems for several subsystems of the Ideal Proof System (IPS), an algebraic proof system introduced by Grochow and Pitassi (J. ACM, 2018). S…
Ideals, Macaulay Bases, and PCPs
Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan +2
All known proofs of the PCP theorem rely on multiple "composition" steps, where PCPs over large alphabets are turned into PCPs over much smaller alphabets at a (relatively) small p…
Eigenvalue Bounds for Symmetric Markov Chains on Multislices With Applications
Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan +1
We consider random walks on ``balanced multislices'' of any ``grid'' that respects the ``symmetries'' of the grid, and show that a broad class of such walks are good spectral expan…
A Near-Optimal Polynomial Distance Lemma Over Boolean Slices
Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan +1
The celebrated Ore-DeMillo-Lipton-Schwartz-Zippel (ODLSZ) lemma asserts that n-variate non-zero polynomial functions of degree d over a field are non-zero over any "gr…
New Bounds for the Ideal Proof System in Positive Characteristic
Amik Raj Behera, Nutan Limaye, Varun Ramanathan +1
In this work, we prove upper and lower bounds over fields of positive characteristics for several fragments of the Ideal Proof System (IPS), an algebraic proof system introduced by…
Low Degree Local Correction Over the Boolean Cube
Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar +2
In this work, we show that the class of multivariate degree- polynomials mapping to any Abelian group is locally correctable with $\widetilde{O}_{d}((\log n)^{…
Local Correction of Linear Functions over the Boolean Cube
Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar +2
We consider the task of locally correcting, and locally list-correcting, multivariate linear functions over the domain over arbitrary fields and more generally Abelian…