Research article:
Samuel R. Buss.
"Lower Bounds on Nullstellensatz Proofs Via Designs."
In Proof Complexity and Feasible Arithmetics,
S. Buss and P. Beame, eds.,
American Mathematical Society, Providence, RI, 1998, pp. 59-71.
Download article: postscript or PDF.
Abstract: The Nullstellensatz proof system is a proof system for propositional logic based on algebraic identities in fields. Prior work has proved lower bounds of the degree Nullstellensatz refutations using combinatorial constructions called designs. This paper surveys the use of designs for Nullstellensatz lower bounds. We give a new, more general definition of designs. We present an explicit construction of designs which give a linear lower bound on the degree of Nullstellensatz proofs of the housesitting principle. Our designs for the housesitting principle work over any ring.