Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures | 11 | 0.54 | 2012 |
Lower Bounds for Lov[a-acute]sz--Schrijver Systems and Beyond Follow from Multiparty Communication Complexity | 7 | 0.47 | 2007 |
The Complexity of Propositional Proofs | 37 | 1.18 | 2007 |
On the Relative Efficiency of Resolution-Like Proofs and Ordered Binary Decision Diagram Proofs | 4 | 0.46 | 2007 |
Nearly-Exponential Size Lower Bounds for Symbolic Quantifier Elimination Algorithms and OBDD-Based Proofs of Unsatisfiability | 4 | 0.40 | 2007 |
A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness | 20 | 1.03 | 2006 |
Formula Caching in DPLL | 5 | 0.42 | 2006 |
Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity | 27 | 0.84 | 2005 |
A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness | 10 | 0.61 | 2005 |
Exponential separation between Res(k) and Res(k+1) for k leq varepsilonlogn | 0 | 0.34 | 2005 |
A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution | 34 | 1.17 | 2004 |
Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations | 2 | 0.38 | 2003 |
Memoization and DPLL: formula caching proof systems | 20 | 1.68 | 2003 |
A Switching Lemma for Small Restrictions and Lower Bounds for k - DNF Resolution | 42 | 1.34 | 2002 |
Bounded-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations | 0 | 0.34 | 2002 |