Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-FeedNext next

TR25-099 | 17th July 2025
Ian Orzel, Srikanth Srinivasan, Sébastien Tavenas, Amir Yehudayoff

The Algebraic Cost of a Boolean Sum

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 >>>


TR25-098 | 13th July 2025
Prerona Chatterjee, Utsab Ghosal, Partha Mukhopadhyay, Amit Sinhababu

IPS Lower Bounds for Formulas and Sum of1 ROABPs

Revisions: 1

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 >>>


TR25-097 | 16th July 2025
Hadar Strauss

On the Limits of Computationally Sound IPPs in the Isolated Model

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 >>>



Next next


ISSN 1433-8092 | Imprint