Please note: This is a beta version of the new dblp website.
You can find the classic dblp view of this page here.
You can find the classic dblp view of this page here.
Nathan Segerlind
2010 – today
- 2012
[j8]Toniann Pitassi, Nathan Segerlind: Exponential Lower Bounds and Integrality Gaps for Tree-Like Lovász-Schrijver Procedures. SIAM J. Comput. 41(1): 128-159 (2012)- 2010
- [j7]Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind: Formula Caching in DPLL. TOCT 1(3) (2010)
2000 – 2009
- 2009
- [c8]Toniann Pitassi, Nathan Segerlind: Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures. SODA 2009: 355-364
- 2008
- [c7]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
- [j6]Nathan Segerlind: The Complexity of Propositional Proofs. Bulletin of Symbolic Logic 13(4): 417-481 (2007)
- [j5]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)
- [i7]Nathan Segerlind: Nearly-Exponential Size Lower Bounds for Symbolic Quantifier Elimination Algorithms and OBDD-Based Proofs of Unsatisfiability. CoRR abs/cs/0701054 (2007)
- [i6]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)
- [i5]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)
- [i4]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)
- 2006
- [j4]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)
- [j3]Russell Impagliazzo, Nathan Segerlind: Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations. ACM Trans. Comput. Log. 7(2): 199-218 (2006)
- [i3]Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind: Formula Caching in DPLL. Electronic Colloquium on Computational Complexity (ECCC) 13(140) (2006)
- 2005
- [j2]Nathan Segerlind: Exponential separation between Res(k) and Res(k+1) for k leq varepsilonlogn. Inf. Process. Lett. 93(4): 185-190 (2005)
- [c6]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
- [c5]Paul Beame, Toniann Pitassi, Nathan Segerlind: Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity. ICALP 2005: 1176-1188
- [i2]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)
- 2004
- [j1]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
- [c4]Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind: Memoization and DPLL: Formula Caching Proof Systems. IEEE Conference on Computational Complexity 2003: 248-
- [i1]Russell Impagliazzo, Nathan Segerlind: Constant-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations. CoRR cs.CC/0308012 (2003)
- 2002
- [c3]Nathan Segerlind, Samuel R. Buss, Russell Impagliazzo: A Switching Lemma for Small Restrictions and Lower Bounds for k - DNF Resolution. FOCS 2002: 604-
- [c2]Russell Impagliazzo, Nathan Segerlind: Bounded-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations. ICALP 2002: 208-219
- 2001
- [c1]Russell Impagliazzo, Nathan Segerlind: Counting Axioms Do Not Polynomially Simulate Counting Gates. FOCS 2001: 200-209
Coauthor Index
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2012-12-08 21:02 CET by the dblp team