Nathan Segerlind

23 papers A* 5A 3Journal 15
YearRankTypeTitle / Venue / Authors
2012 J jnl
Exponential Lower Bounds and Integrality Gaps for Tree-Like Lovász-Schrijver Procedures.
SIAM J. Comput.
Toniann Pitassi, Nathan Segerlind
2010 J jnl
Formula Caching in DPLL.
ACM Trans. Comput. Theory
Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind
2009 A* conf
Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures.
SODA
Toniann Pitassi, Nathan Segerlind
2008 A conf
On the Relative Efficiency of Resolution-Like Proofs and Ordered Binary Decision Diagram Proofs.
CCC
Nathan Segerlind
2007 J jnl
Exponential lower bounds and integrality gaps for tree-like Lovasz-Schrijver procedures.
Electron. Colloquium Comput. Complex.
Nathan Segerlind, Toniann Pitassi
2007 J jnl
Lower Bounds for Lov[a-acute]sz--Schrijver Systems and Beyond Follow from Multiparty Communication Complexity.
SIAM J. Comput.
Paul Beame, Toniann Pitassi, Nathan Segerlind
2007 J jnl
Nearly-Exponential Size Lower Bounds for Symbolic Quantifier Elimination Algorithms and OBDD-Based Proofs of Unsatisfiability
CoRR
Nathan Segerlind
2007 J jnl
Nearly-Exponential Size Lower Bounds for Symbolic Quantifier Elimination Algorithms and OBDD-Based Proofs of Unsatisfiability.
Electron. Colloquium Comput. Complex.
Nathan Segerlind
2007 J jnl
On the relative efficiency of resolution-like proofs and ordered binary decision diagram proofs.
Electron. Colloquium Comput. Complex.
Nathan Segerlind
2007 J jnl
The Complexity of Propositional Proofs.
Bull. Symb. Log.
Nathan Segerlind
2006 J jnl
A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness.
Comput. Complex.
Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson
2006 J jnl
Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations.
ACM Trans. Comput. Log.
Russell Impagliazzo, Nathan Segerlind
2006 J jnl
Formula Caching in DPLL.
Electron. Colloquium Comput. Complex.
Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind
2005 A conf
A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness.
CCC
Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson
2005 J jnl
Exponential separation between Res(
Inf. Process. Lett.
Nathan Segerlind
2005 A* conf
Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity.
ICALP
Paul Beame, Toniann Pitassi, Nathan Segerlind
2005 J jnl
Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty communication complexity
Electron. Colloquium Comput. Complex.
Paul Beame, Toniann Pitassi, Nathan Segerlind
2004 J jnl
A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution.
SIAM J. Comput.
Nathan Segerlind, Samuel R. Buss, Russell Impagliazzo
2003 J jnl
Constant-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations
CoRR
Russell Impagliazzo, Nathan Segerlind
2003 A conf
Memoization and DPLL: Formula Caching Proof Systems.
CCC
Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind
2002 A* conf
A Switching Lemma for Small Restrictions and Lower Bounds for k - DNF Resolution.
FOCS
Nathan Segerlind, Samuel R. Buss, Russell Impagliazzo
2002 A* conf
Bounded-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations.
ICALP
Russell Impagliazzo, Nathan Segerlind
2001 A* conf
Counting Axioms Do Not Polynomially Simulate Counting Gates.
FOCS
Russell Impagliazzo, Nathan Segerlind