Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Ideal Proof System:
TR16-098 | 16th June 2016
Michael Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson

Proof Complexity Lower Bounds from Algebraic Circuit Complexity

We give upper and lower bounds on the power of subsystems of the Ideal Proof System (IPS), the algebraic proof system recently proposed by Grochow and Pitassi, where the circuits comprising the proof come from various restricted algebraic circuit classes. This mimics an established research direction in the ... more >>>

TR21-172 | 1st December 2021
Robert Andrews, Michael Forbes

Ideals, Determinants, and Straightening: Proving and Using Lower Bounds for Polynomial Ideals

We show that any nonzero polynomial in the ideal generated by the $r \times r$ minors of an $n \times n$ matrix $X$ can be used to efficiently approximate the determinant. Specifically, for any nonzero polynomial $f$ in this ideal, we construct a small depth-three $f$-oracle circuit that approximates the ... more >>>

ISSN 1433-8092 | Imprint