IEEE - Institute of Electrical and Electronics Engineers, Inc. - Random CNFs are hard for the polynomial calculus

40th Annual Symposium on Foundations of Computer Science

Author(s): Ben-Sasson, E. ; Impagliazzo, R.
Publisher: IEEE - Institute of Electrical and Electronics Engineers, Inc.
Publication Date: 1 January 1999
Conference Location: New York City, NY, USA, USA
Conference Date: 17 October 1999
Page(s): 415 - 421
ISBN (Paper): 0-7695-0409-4
ISSN (Paper): 0272-5428
DOI: 10.1109/SFFCS.1999.814613
Regular:

We show a general reduction that derives lower bounds on degrees of polynomial calculus proofs of tautologies, over any field of characteristic (other than 2) from lower bounds for resolution... View More

Advertisement