On the Complexity of Modulo-q Arguments and the Chevalley-Warning Theorem

Abstract

We study the search problem class ${\mathrm{PPA}}_q$ defined as a modulo-$q$ analog of the well-known $\text{polynomial parity argument}$ class $\mathrm{PPA}$ introduced by Papadimitriou '94. Our first result shows that this class can be characterized in terms of ${\mathrm{PPA}}_p$ for prime $p$. Our main result is to establish that an $\text{explicit}$ version of a search problem associated to the Chevalley--Warning theorem is complete for ${\mathrm{PPA}}_p$ for prime $p$. This problem is $\text{natural}$ in that it does not explicitly involve circuits as part of the input. It is the first such complete problem for ${\mathrm{PPA}}_p$ when $p\ge 3$. Finally we discuss connections between Chevalley-Warning theorem and the well-studied $\text{short integer solution}$ problem and survey the structural properties of ${\mathrm{PPA}}_q$.

To appear at the Computational Complexity Conference (CCC) 2020