Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleRandom CNF’s are Hard for the Polynomial Calculus
Author(s) Eli Ben-Sasson, Russell Impagliazzo
TypeArticle in Journal
AbstractWe 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.
KeywordsPropositional proof complexity, polynomial calculus, Groebner basis, random CNF formulae
ISSN1016-3328; 1420-8954/e
URL http://link.springer.com/article/10.1007%2Fs00037-010-0293-1
JournalComput. Complexity
PublisherSpringer (Birkh\"auser), Basel
Translation No
Refereed No