 | 2009 |
|---|
| 21 |       | Toniann Pitassi,
Nathan Segerlind:
Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures.
SODA 2009: 355-364 |
| 2008 |
|---|
| 20 | | Nathan Segerlind:
On the Relative Efficiency of Resolution-Like Proofs and Ordered Binary Decision Diagram Proofs.
IEEE Conference on Computational Complexity 2008: 100-111 |
| 2007 |
|---|
| 19 | | Nathan Segerlind:
The Complexity of Propositional Proofs.
Bulletin of Symbolic Logic 13(4): 417-481 (2007) |
| 18 | | Nathan Segerlind:
Nearly-Exponential Size Lower Bounds for Symbolic Quantifier Elimination Algorithms and OBDD-Based Proofs of Unsatisfiability
CoRR abs/cs/0701054: (2007) |
| 17 | | Nathan Segerlind:
Nearly-Exponential Size Lower Bounds for Symbolic Quantifier Elimination Algorithms and OBDD-Based Proofs of Unsatisfiability.
Electronic Colloquium on Computational Complexity (ECCC) 14(009): (2007) |
| 16 | | Nathan Segerlind,
Toniann Pitassi:
Exponential lower bounds and integrality gaps for tree-like Lovasz-Schrijver procedures.
Electronic Colloquium on Computational Complexity (ECCC) 14(107): (2007) |
| 15 | | Nathan Segerlind:
On the relative efficiency of resolution-like proofs and ordered binary decision diagram proofs.
Electronic Colloquium on Computational Complexity (ECCC) 14(126): (2007) |
| 14 | | Paul Beame,
Toniann Pitassi,
Nathan Segerlind:
Lower Bounds for Lov[a-acute]sz--Schrijver Systems and Beyond Follow from Multiparty Communication Complexity.
SIAM J. Comput. 37(3): 845-869 (2007) |
| 2006 |
|---|
| 13 | | Russell Impagliazzo,
Nathan Segerlind:
Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations.
ACM Trans. Comput. Log. 7(2): 199-218 (2006) |
| 12 | | Paul Beame,
Toniann Pitassi,
Nathan Segerlind,
Avi Wigderson:
A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness.
Computational Complexity 15(4): 391-432 (2006) |
| 11 | | Paul Beame,
Russell Impagliazzo,
Toniann Pitassi,
Nathan Segerlind:
Formula Caching in DPLL.
Electronic Colloquium on Computational Complexity (ECCC) 13(140): (2006) |
| 2005 |
|---|
| 10 | | Paul Beame,
Toniann Pitassi,
Nathan Segerlind:
Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity.
ICALP 2005: 1176-1188 |
| 9 | | Paul Beame,
Toniann Pitassi,
Nathan Segerlind,
Avi Wigderson:
A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness.
IEEE Conference on Computational Complexity 2005: 52-66 |
| 8 | | Paul Beame,
Toniann Pitassi,
Nathan Segerlind:
Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty communication complexity
Electronic Colloquium on Computational Complexity (ECCC)(053): (2005) |
| 7 | | Nathan Segerlind:
Exponential separation between Res(k) and Res(k+1) for k leq varepsilonlogn.
Inf. Process. Lett. 93(4): 185-190 (2005) |
| 2004 |
|---|
| 6 | | Nathan Segerlind,
Samuel R. Buss,
Russell Impagliazzo:
A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution.
SIAM J. Comput. 33(5): 1171-1200 (2004) |
| 2003 |
|---|
| 5 | | Paul Beame,
Russell Impagliazzo,
Toniann Pitassi,
Nathan Segerlind:
Memoization and DPLL: Formula Caching Proof Systems.
IEEE Conference on Computational Complexity 2003: 248- |
| 4 | | Russell Impagliazzo,
Nathan Segerlind:
Constant-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations
CoRR cs.CC/0308012: (2003) |
| 2002 |
|---|
| 3 | | Nathan Segerlind,
Samuel R. Buss,
Russell Impagliazzo:
A Switching Lemma for Small Restrictions and Lower Bounds for k - DNF Resolution.
FOCS 2002: 604- |
| 2 | | Russell Impagliazzo,
Nathan Segerlind:
Bounded-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations.
ICALP 2002: 208-219 |
| 2001 |
|---|
| 1 |  | Russell Impagliazzo,
Nathan Segerlind:
Counting Axioms Do Not Polynomially Simulate Counting Gates.
FOCS 2001: 200-209 |
