Details:
Title | | Author(s) | Eli Ben-Sasson, Russell Impagliazzo | Type | Article in Journal | Abstract | We prove linear lower bounds on the Polynomial Calculus (PC) refutation-degree of random CNF whenever the underlying field has characteristic greater than 2. Our proof follows by showing the PC refutation-degree of a unsatisfiable system of linear equations modulo 2 is equivalent to its Gaussian width, a concept defined by the late Mikhail Alekhnovich.
The equivalence of refutation-degree and Gaussian width which is the main contribution of this paper, allows us to also simplify the refutation-degree lower bounds of Buss et al. (2001) and additionally prove non-trivial upper bounds on the resolution and PC complexity of refuting unsatisfiable systems of linear equations. | Keywords | Propositional proof complexity, polynomial calculus, Groebner basis, random CNF formulae | ISSN | 1016-3328; 1420-8954/e |
URL |
http://link.springer.com/article/10.1007%2Fs00037-010-0293-1 |
Language | English | Journal | Comput. Complexity | Volume | 19 | Number | 4 | Pages | 501--519 | Publisher | Springer (Birkh\"auser), Basel | Year | 2010 | Edition | 0 | Translation |
No | Refereed |
No |
|