Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > POLYNOMIALCALCULUS:
Reports tagged with polynomialcalculus:
TR97-042 | 22nd September 1997
Russell Impagliazzo, Pavel Pudlak, Jiri Sgall

Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm

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




ISSN 1433-8092 | Imprint