Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > IDEAL PROOF SYSTEM:
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