Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Nullstellensatz:
TR01-011 | 21st January 2001
Dima Grigoriev, Edward Hirsch

Algebraic proof systems over formulas

We introduce two algebraic propositional proof systems F-NS
and F-PC. The main difference of our systems from (customary)
Nullstellensatz and Polynomial Calculus is that the polynomials
are represented as arbitrary formulas (rather than sums of
monomials). Short proofs of Tseitin's tautologies in the
constant-depth version of F-NS provide ... more >>>

TR16-064 | 19th April 2016
Stephen A. Cook, Toniann Pitassi, Robert Robere, Benjamin Rossman

Exponential Lower Bounds for Monotone Span Programs

Monotone span programs are a linear-algebraic model of computation which were introduced by Karchmer and Wigderson in 1993. They are known to be equivalent to linear secret sharing schemes, and have various applications in complexity theory and cryptography. Lower bounds for monotone span programs have been difficult to obtain because ... more >>>

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

TR17-165 | 3rd November 2017
Toniann Pitassi, Robert Robere

Lifting Nullstellensatz to Monotone Span Programs over Any Field

We characterize the size of monotone span programs computing certain "structured" boolean functions by the Nullstellensatz degree of a related unsatisfiable Boolean formula.

This yields the first exponential lower bounds for monotone span programs over arbitrary fields, the first exponential separations between monotone span programs over fields of different ... more >>>

TR21-182 | 30th December 2021
Ilario Bonacina, Maria Luisa Bonet

On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems

The propositional proof system Sherali-Adams (SA) has polynomial-size proofs of the pigeonhole principle (PHP). Similarly, the Nullstellensatz (NS) proof system has polynomial size proofs of the bijective (i.e. both functional and onto) pigeonhole principle (ofPHP). We characterize the strength of these algebraic proof systems in terms of Boolean proof systems ... more >>>

ISSN 1433-8092 | Imprint