ECCC-Report TR97-042https://eccc.weizmann.ac.il/report/1997/042Comments and Revisions published for TR97-042en-usMon, 22 Sep 1997 15:04:22 +0200
Paper TR97-042
| Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm |
Russell Impagliazzo,
Pavel Pudlak,
Jiri Sgall
https://eccc.weizmann.ac.il/report/1997/042Razborov~\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.
Mon, 22 Sep 1997 15:04:22 +0200https://eccc.weizmann.ac.il/report/1997/042