Linear gaps between degrees for the polynomial calculus modulo distinct primes
Sam Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi · 1999
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 >_ 2. The lower bounds apply to the polynomial calculus over fields or rings.These are the first linear lower bounds for polynomial calculus; moreover, they distinguish linearly between proofs over fields of characteristic p and T, y # r, and more generally distinguish linearly the rings Z, and Z, where 4 and P do not have the identical prime factors.