Nathan Segerlind

Publication Activity (10 Years)

Years Active: 2001-2012
Publications (10 Years): 0

Top Topics

Linear Programming Relaxation

Top Venues

SIAM J. Comput.

Publications

Toniann Pitassi, Nathan Segerlind
Exponential Lower Bounds and Integrality Gaps for Tree-Like Lovász-Schrijver Procedures. SIAM J. Comput. 41 (1) (2012)
Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind
Formula Caching in DPLL. ACM Trans. Comput. Theory 1 (3) (2010)
Toniann Pitassi, Nathan Segerlind
Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures. SODA (2009)
Nathan Segerlind
On the Relative Efficiency of Resolution-Like Proofs and Ordered Binary Decision Diagram Proofs. Computational Complexity Conference (2008)
Nathan Segerlind
Nearly-Exponential Size Lower Bounds for Symbolic Quantifier Elimination Algorithms and OBDD-Based Proofs of Unsatisfiability CoRR (2007)
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) (2007)
Nathan Segerlind
Nearly-Exponential Size Lower Bounds for Symbolic Quantifier Elimination Algorithms and OBDD-Based Proofs of Unsatisfiability. Electron. Colloquium Comput. Complex. 14 (009) (2007)
Nathan Segerlind
The Complexity of Propositional Proofs. Bull. Symb. Log. 13 (4) (2007)
Nathan Segerlind
On the relative efficiency of resolution-like proofs and ordered binary decision diagram proofs. Electron. Colloquium Comput. Complex. 14 (126) (2007)
Nathan Segerlind, Toniann Pitassi
Exponential lower bounds and integrality gaps for tree-like Lovasz-Schrijver procedures. Electron. Colloquium Comput. Complex. 14 (107) (2007)
Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson
A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness. Comput. Complex. 15 (4) (2006)
Russell Impagliazzo, Nathan Segerlind
Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations. ACM Trans. Comput. Log. 7 (2) (2006)
Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind
Formula Caching in DPLL. Electron. Colloquium Comput. Complex. 13 (140) (2006)
Paul Beame, Toniann Pitassi, Nathan Segerlind
Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity. ICALP (2005)
Nathan Segerlind
. Inf. Process. Lett. 93 (4) (2005)
Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson
A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness. Computational Complexity Conference (2005)
Paul Beame, Toniann Pitassi, Nathan Segerlind
Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty communication complexity Electron. Colloquium Comput. Complex. (053) (2005)
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) (2004)
Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind
Memoization and DPLL: Formula Caching Proof Systems. Computational Complexity Conference (2003)
Russell Impagliazzo, Nathan Segerlind
Constant-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations CoRR (2003)
Nathan Segerlind, Samuel R. Buss, Russell Impagliazzo
A Switching Lemma for Small Restrictions and Lower Bounds for k - DNF Resolution. FOCS (2002)
Russell Impagliazzo, Nathan Segerlind
Bounded-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations. ICALP (2002)
Russell Impagliazzo, Nathan Segerlind
Counting Axioms Do Not Polynomially Simulate Counting Gates. FOCS (2001)