Counting Axioms Do Not Polynomially Simulate Counting Gates. - Russell Impagliazzo; Nathan Segerlind (FOCS, 2001)

Bounded-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations. - Russell Impagliazzo; Nathan Segerlind (ICALP, 2002)

Memoization and DPLL: Formula Caching Proof Systems. - Paul Beame; Russell Impagliazzo; Toniann Pitassi; Nathan Segerlind (CCC, 2003)

A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution. - Nathan Segerlind; Samuel R. Buss; Russell Impagliazzo (SIAM J. Comput., 2004)

A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness. - Paul Beame; Toniann Pitassi; Nathan Segerlind; Avi Wigderson (CCC, 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)

Exponential separation between Res(k) and Res(k+1) for k leq varepsilonlogn. - Nathan Segerlind (Inf. Process. Lett., 2005)

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)

Formula Caching in DPLL. - Paul Beame; Russell Impagliazzo; Toniann Pitassi; Nathan Segerlind (Electron. Colloquium Comput. Complex., 2006)

Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations. - Russell Impagliazzo; Nathan Segerlind (ACM Trans. Comput. Log., 2006)

The Complexity of Propositional Proofs. - Nathan Segerlind (Bull. Symb. Log., 2007)

Nearly-Exponential Size Lower Bounds for Symbolic Quantifier Elimination Algorithms and OBDD-Based Proofs of Unsatisfiability. - Nathan Segerlind (Electron. Colloquium Comput. Complex., 2007)

On the relative efficiency of resolution-like proofs and ordered binary decision diagram proofs. - Nathan Segerlind (Electron. Colloquium Comput. Complex., 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)

Exponential Lower Bounds and Integrality Gaps for Tree-Like Lovász-Schrijver Procedures. - Toniann Pitassi; Nathan Segerlind (SIAM J. Comput., 2012)