It is a well-known fact that the permanent polynomial is complete for the complexity class VNP, and it is largely suspected that the determinant does not share this property, despite its similar expression.
We study the question of why the VNP-completeness proof of the permanent fails for the determinant.
We ... more >>>

We give new lower bounds for the fragments of the Ideal Proof System (IPS) introduced by Grochow and Pitassi (JACM 2018). The Ideal Proof System is a central topic in algebraic proof complexity developed in the context of Nullstellensatz refutation (Beame, Impagliazzo, Krajicek, Pitassi, Pudlak, FOCS 1994) and simulates Extended ... more >>>

Interactive proofs of proximity (IPPs) are a relaxation of interactive proofs, analogous to property testing, in which soundness is required to hold only for inputs that are far from the property being verified. In such proof systems, the verifier has oracle access to the input, and it engages in two ... more >>>