3 papers
cs.CC2026
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…
cs.CC2026
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…
cs.CC2025
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…