Journal article:

Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, and Toniann Pitassi.
"Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Degrees."
Journal of Computer and System Sciences 62 (2001) 267-289.

Download journal article version: postscript or PDF

Conference proceedings (earlier version).

Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, and Toniann Pitassi.
"Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Degrees."
Proceedings, Thirty-First Annual ACM Symposium of Theory of Computing (STOC) 1999, pages 547-556.

Download conference proceedings extended abstract: postscript or PDF.

Conference abstract.

Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, and Toniann Pitassi.
"Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Degrees (Abstract)."
Proceedings, Fourteenth Annual IEEE Conference on Complexity Conference (LCC'99)}, 1999, pp. 5-5.

Download Complexity Conference proceedings one page abstract: postscript or PDF.

Journal version abstract: This paper gives nearly optimal lower bounds on the minimum degree of polynomial calculus refutations of Tseitin's graph tautologies and the mod~\$p\$ counting principles, \$p\ge 2\$.  The lower bounds apply to the polynomial calculus over fields or rings.  These are the first linear lower bounds for the polynomial calculus for \$k\$-CNF formulas. As a consequence, it follows that the Gr\"obner basis algorithm, used as a heuristic for \$k\$-SAT, requires exponential time in the worst-case.  Moreover, our lower bounds distinguish linearly between proofs over fields of characteristic \$q\$ and \$r\$, \$q\not= r\$, and more generally distinguish linearly the rings \$Z_q\$ and \$Z_r\$ where \$q\$~and~\$r\$ do not have the identical prime factors.

Back to Sam Buss's publications page.