✦ LIBER ✦
Linear Gaps between Degrees for the Polynomial Calculus Modulo Distinct Primes
✍ Scribed by Sam Buss; Dima Grigoriev; Russell Impagliazzo; Toniann Pitassi
- Publisher
- Elsevier Science
- Year
- 2001
- Tongue
- English
- Weight
- 214 KB
- Volume
- 62
- Category
- Article
- ISSN
- 0022-0000
No coin nor oath required. For personal study only.
✦ Synopsis
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 the polynomial calculus for k-CNF formulas. As a consequence, it follows that