Nathan Segerlind

According to our database, Nathan Segerlind authored at least 15 papers between 2001 and 2012.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2012

Exponential Lower Bounds and Integrality Gaps for Tree-Like Lovász-Schrijver Procedures.

Toniann Pitassi, Nathan Segerlind

SIAM J. Comput., 2012

2007

Lower Bounds for Lov[a-acute]sz--Schrijver Systems and Beyond Follow from Multiparty Communication Complexity.

Paul Beame, Toniann Pitassi, Nathan Segerlind

SIAM J. Comput., 2007

On the relative efficiency of resolution-like proofs and ordered binary decision diagram proofs.

Nathan Segerlind

Electron. Colloquium Comput. Complex., 2007

Nearly-Exponential Size Lower Bounds for Symbolic Quantifier Elimination Algorithms and OBDD-Based Proofs of Unsatisfiability.

Nathan Segerlind

Electron. Colloquium Comput. Complex., 2007

The Complexity of Propositional Proofs.

Nathan Segerlind

Bull. Symb. Log., 2007

2006

Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations.

Russell Impagliazzo, Nathan Segerlind

ACM Trans. Comput. Log., 2006

Formula Caching in DPLL.

Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind

Electron. Colloquium Comput. Complex., 2006

A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness.

Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson

Comput. Complex., 2006

2005

Exponential separation between Res(<i>k</i>) and Res(<i>k</i>+1) for <i>k</i> leq varepsilonlog<i>n</i>.

Nathan Segerlind

Inf. Process. Lett., 2005

Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty communication complexity

Paul Beame, Toniann Pitassi, Nathan Segerlind

Electron. Colloquium Comput. Complex., 2005

A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness.

Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004

A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution.

Nathan Segerlind, Samuel R. Buss, Russell Impagliazzo

SIAM J. Comput., 2004

2003

Memoization and DPLL: Formula Caching Proof Systems.

Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

Bounded-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations.

Russell Impagliazzo, Nathan Segerlind

Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

2001

Counting Axioms Do Not Polynomially Simulate Counting Gates.

Russell Impagliazzo, Nathan Segerlind

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001