Paper Info
Title
Strong ETH holds for regular resolution
Abstract
We obtain asymptotically sharper lower bounds on resolution complexity for k-CNF's than was known previously. We show that for any large enough k there are k-CNF's which require resolution width (1-~O(k-1/4))n, regular resolution size 2(1-~O(k-1/4))n, and general resolution size (3/2)(1-~O(k-1/4))n.
Year
DOI
Venue
2013
10.1145/2488608.2488669
STOC
Keywords
Field
DocType
sharper lower bound,large enough k,resolution complexity,resolution width,regular resolution size,strong eth,general resolution size,proof complexity,resolution
Discrete mathematics,Combinatorics,Proof complexity,Mathematics
Conference
Citations 
PageRank 
References 
6
0.48
29
Authors
2
Name
Order
Citations
PageRank
Christopher Beck1271.53
Russell Impagliazzo25444482.13