Research Articles

Nathan Segerlind

 

This is my publication and research web page.  Papers have been included in the pdf format. For papers that are too recent  to appear here, please email me.


Copyright notice:  All material downloadable from this page is copyrighted by Nathan Segerlind, his coauthors, and/or the publishers.  

 

 

Summary of Research Articles - journal articles,  conference proceedings and preprints.

  1. On the relative efficiency of resolution-like proofs and ordered binary decision diagram proofs.  To appear in the Twenty-third Conference on Computational Complexity, 2008.
  2. Exponential lower bounds and integrality gaps for tree-like Lovasz-Schrijver procedures.  With Toni Pitassi. Preprint, 2007.  Available as ECCC Tech Report 07-107 at  http://eccc.hpi-web.de/eccc-reports/2007/TR07-107/index.html  Submitted.
  3. The Complexity of Propositional Proofs  The Bulletin of Symbolic Logic, volume 13, number 4, pages 482-537, 2007.
  4. Nearly-exponential size lower bounds for symbolic quantifier elimination algorithms and OBDD-based proofs of unsatisfiability.   Preprint, 2007.   Available as ECCC Tech Report 07-009 at http://eccc.hpi-web.de/eccc-reports/2007/TR07-009/index.html Submitted.
  5. Lower Bounds for Lovasz-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity .  With Paul Beame and Toni Pitassi.   SIAM Journal on Computing, volume 37, number 3, pages 845-869, 2006. Conference version in ICALP 2005.
  6. A Strong Direct Product Lemma for Corruption and the Multiparty NOF Communication Complexity of Disjointness.  With Paul Beame, Toni Pitassi,  and Avi Wigderson.   Journal of Computational Complexity, volume 15, number 4, pages 391-432, 2006  (A special issue of selections from the 2005 Conference on Computational Complexity)  Conference version:  A Direct Sum for Corruption and the Multiparty Communication Complexity of Set-Disjointness,  CCC 2005.
  7. An Exponential Separation Between Res(k+1) and Res(k) for k ≤ ε logn .    Information Processing Letters,  93(4),  pages 185-190, 2005.
  8. Formula Caching in DPLL. With P. Beame,   R. Impagliazzo,  and T. Pitassi.   Journal version submitted,  preprint available as ECCC Tech Report 06-140 at http://eccc.hpi-web.de/eccc-reports/2006/TR06-140/index.html. Conference version: Memoization and DPLL:  Formula Caching Proof Systems, CCC 2003.
  9. A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution.  With Sam Buss and Russell Impagliazzo.    SIAM J. Computing 33 (5),  1171-1200 (2004).  Conference version in FOCS 2002.
  10. Bounded-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations.  With Russell Impagliazzo.   ACM Transactions on Computational. Logic 7 (2), 199-218 (2006).  Conference version in ICALP  2002. 
  11. Counting Axioms Do Not Polynomially Simulate Counting Gates.  With Russell Impagliazzo.     Latest revision:  06/2003. Extended abstract in Proceedings of the Forty-second Annual Symposium on Foundations of Computer Science, IEEE Computer Society, 2001, pp. 200-209. 


 

 

Ph.D. Thesis:

  1. New Separations in Propositional Proof Complexity,  Department of Computer Science,   University of California at San Diego,  2003. 151+xii pages.  Advisors Sam Buss and Russell Impagliazzo. (Winner of the Association of Symbolic Logic’s 2004 Sacks Prize for Outstanding Doctoral Dissertation in Logic and the European Computer Science Logic Association's 2005 Ackermann Award for Outstanding Doctoral Dissertation in Computer Science Logic.)

                       

Acknowledgement: The bulk of the work on this page was performed with partial financial support from various NSF grants.