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