Neil Thapen

Institute of Mathematics, AS CR
Žitná 25, 115 67 Praha 1
Czech Republic

I am a researcher at the Institute of Mathematics of the Academy of Sciences of the Czech Republic. My research is mostly in logic, in particular proof complexity and weak arithmetic.

I organize the institute's logic seminar.

Published papers/preprints

These may differ from the final published versions.
  1. The space complexity of cutting planes refutations (pdf)
    Nicola Galesi, Pavel Pudlák, Neil Thapen. ECCC Technical Report TR14-138, 2014.

  2. A trade-off between length and width in resolution (pdf)
    Neil Thapen. ECCC Technical Report TR14-137, 2014.

  3. Total space in resolution (pdf)
    Ilario Bonacina, Nicola Galesi, Neil Thapen. FOCS 2014.

  4. The Ordering Principle in a Fragment of Approximate Counting (pdf)
    Albert Atserias and Neil Thapen. ACM Transactions on Computational Logic, Vol 15:4, article 29, 2014.

  5. Fragments of approximate counting (pdf)
    Samuel Buss, Leszek Kołodziejczyk and Neil Thapen. Journal of Symbolic Logic, Vol 79:2, pages 496-525, 2014.
    [An open problem from this paper is solved in "The Ordering Principle in a Fragment of Approximate Counting" above.]

  6. Parity games and propositional proofs (pdf)
    Arnold Beckmann, Pavel Pudlák and Neil Thapen. ACM Transactions on Computational Logic, Vol 15:2, article 17, 2014.

  7. How much randomness is needed for statistics? (pdf)
    Bjørn Kjos-Hanssen, Antoine Taveneaux and Neil Thapen. Annals of Pure and Applied Logic, Vol 165:9, pages 1470-1483, 2014.
    An earlier version appeared in Computability in Europe 2012, LNCS Vol 7318, pages 395-404, 2012.

  8. The complexity of proving that a graph is Ramsey (pdf)
    Massimo Lauria, Pavel Pudlák, Vojtěch Rödl and Neil Thapen. Proceedings of ICALP 2013, LNCS Vol 7965, pages 648-695, 2013.

  9. Space Complexity in Polynomial Calculus (pdf)
    Yuval Filmus, Massimo Lauria, Jakob Nordström, Neil Thapen and Noga Ron-Zewi. ECCC Technical Report TR12-132, 2012.
    An earlier version appeared in IEEE Conference on Computational Complexity 2012, pages 334-344. (pdf)

  10. Alternating minima and maxima, Nash equilibria and Bounded Arithmetic (pdf)
    Pavel Pudlák and Neil Thapen. Annals of Pure and Applied Logic, Vol 163:5, pages 604-614, 2012.

  11. Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem (pdf)
    Neil Thapen. Archive for Mathematical Logic, Vol 50:7-8, pages 665-680, 2011.

  12. The provably total NP search problems of weak second order bounded arithmetic (pdf)
    Leszek Kołodziejczyk, Phuong Nguyen and Neil Thapen. Annals of Pure and Applied Logic, Vol 162:6, pages 419-446, 2011.

  13. The provably total search problems of bounded arithmetic (pdf)
    Alan Skelley and Neil Thapen. Proceedings of the London Mathematical Society, Vol 103:1, pages 106-138, 2011.

  14. The polynomial and linear hierarchies in V_0 (pdf)
    Leszek Kołodziejczyk and Neil Thapen. Mathematical Logic Quarterly, Vol 55:5, pages 509-514, 2009.
    An earlier version appeared in Computability in Europe 2007.

  15. The polynomial and linear hierarchies in models where the weak pigeonhole principle fails (pdf)
    Leszek Kołodziejczyk and Neil Thapen. Journal of Symbolic Logic, Vol 73:2, pages 578-592, 2008.

  16. NP search problems in low fragments of bounded arithmetic (pdf)
    Jan Krajíček, Alan Skelley and Neil Thapen. Journal of Symbolic Logic, Vol 72:2, pages 649-672, 2007.

  17. The strength of replacement in weak arithmetic (pdf)
    Stephen Cook and Neil Thapen. ACM Transactions on Computational Logic, Vol 7:4, pages 749-764, 2006.
    An earlier version appeared in LICS 2004.

  18. A note on Delta_1 induction and Sigma_1 collection (pdf)
    Neil Thapen. Fundamenta Mathematicae, Vol 186, Pages 79-84, 2005.

  19. Resolution and pebbling games (pdf)
    Nicola Galesi and Neil Thapen. SAT 2005, LNCS 3569, pages 76-90, 2005.

  20. Weak theories of linear algebra (pdf)
    Neil Thapen and Michael Soltys. Archive for Mathematical Logic, Vol 44:2, pages 195-208, 2005.

  21. Structures interpretable in models of bounded arithmetic (pdf)
    Neil Thapen. Annals of Pure and Applied Logic, Vol 136:3, pages 247-266, 2005.

  22. A model-theoretic characterization of the weak pigeonhole principle (pdf)
    Neil Thapen. Annals of Pure and Applied Logic, Vol 118:1-2, pages 175-195, 2002.

Other things

14/11/14 Neil Thapen