Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR97-042 | 22nd September 1997 00:00

Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm


Authors: Russell Impagliazzo, Pavel Pudlak, Jiri Sgall
Publication: 22nd September 1997 15:04
Downloads: 1035


Razborov~\cite{Razborov96} recently proved that polynomial
calculus proofs of the pigeonhole principle $PHP_n^m$ must have
degree at least $\ceiling{n/2}+1$ over any field. We present a
simplified proof of the same result. The main
idea of our proof is the same as in the original proof
of Razborov: we want to describe explicitly the vector space of
the polynomials derivable in a low degree polynomial calculus
refutation of the pigeonhole principle, and the description uses
the pigeon dance as before. We are able to avoid some of the
technical machinery, due to the simple counting argument which
shows that the set of polynomials, which generates the vector
space of consequences, forms its basis.

Furthermore we show a matching upper bound on the polynomial
calculus proofs of the pigeonhole principle for any field of
sufficiently large characteristic,
and an $\ceiling{n/2}+1$ lower bound for any subset sum problem
over the field of reals.

ISSN 1433-8092 | Imprint