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

Details:

   
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
LanguageEnglish
JournalComput. Complexity
Volume19
Number4
Pages501--519
PublisherSpringer (Birkh\"auser), Basel
Year2010
Edition0
Translation No
Refereed No
Webmaster