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 (old page).

Published papers/preprints

These may differ from the final published versions.
  1. Approximate counting and NP search problems (pdf)
    Leszek Kołodziejczyk and Neil Thapen. Journal of Mathematical Logic, Vol 22:3, 2022.

  2. A separation of PLS from PPP (on ECCC)
    Ilario Bonacina and Neil Thapen. ECCC report TR22-089, 2022.

  3. First-order reasoning and efficient semialgebraic proofs (pdf)
    Fedor Part, Neil Thapen and Iddo Tzameret. Proceedings of LICS 2021.

  4. DRAT and propagation redundancy proofs without new variables (pdf)
    Samuel Buss and Neil Thapen. Logical Methods in Computer Science, Vol 17:2, article 12, 2021.
    A version appeared in SAT 2019, pp. 71-89.

  5. Random resolution refutations (pdf)
    Pavel Pudlák, Neil Thapen. Computational Complexity, Vol 28:2, pages 185-239, 2019
    A version appeared in CCC 2017, LIPIcs Vol 79, pages 1:1-1:10, 2015.

  6. Feasible set functions have small circuits (pdf)
    Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller, Neil Thapen. Computability, Vol 8:1, pages 67-98, 2019.

  7. Polynomial calculus space and resolution width (revised pdf)
    Nicola Galesi, Leszek Kołodziejczyk and Neil Thapen. Proceedings of FOCS 2019, pp. 1325–1337, 2019.

  8. On semantic cutting planes proofs with very small coefficients (pdf)
    Massimo Lauria and Neil Thapen. Information Processing Letters, Vol 136, pages 70-75, 2018.

  9. Cobham Recursive Set Functions and Weak Set Theories (pdf)
    Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller, Neil Thapen.
    In Sets and Computations, Lecture Notes Series 33, Institute for Mathematical Sciences, National University of Singapore, pages 55-116, 2017.

  10. The complexity of proving that a graph is Ramsey (pdf)
    Massimo Lauria, Pavel Pudlák, Vojtěch Rödl and Neil Thapen. Combinatorica, Vol 37 (2), pp. 253-268, 2017.
    An earlier version appeared at ICALP 2013, LNCS Vol 7965, pages 648-695, 2013.

  11. A tradeoff between length and width in resolution (pdf)
    Neil Thapen. Theory of Computing, Vol 12:5, pages 1-14, 2016.

  12. Total space in resolution (pdf)
    Ilario Bonacina, Nicola Galesi, Neil Thapen. SIAM Journal on Computing, Vol 45:5, pages 1894-1909, 2016.
    An earlier version appeared in FOCS 2014, pages 641-650.

  13. Cobham Recursive Set Functions (pdf)
    Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller, Neil Thapen. Annals of Pure and Applied Logic, Vol 167:3, pages 335-369, 2016.

  14. Space Complexity in Polynomial Calculus (pdf)
    Yuval Filmus, Massimo Lauria, Jakob Nordström, Neil Thapen and Noga Ron-Zewi. SIAM Journal on computing, Vol 44:4, pages 1119-1153, 2015.
    An earlier version appeared in IEEE Conference on Computational Complexity 2012, pages 334-344.

  15. The space complexity of cutting planes refutations (pdf)
    Nicola Galesi, Pavel Pudlák, Neil Thapen. Proceedings of CCC 2015, LIPIcs Vol 33, pages 433-447, 2015.

  16. 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.

  17. 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.]

  18. 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.

  19. 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.

  20. 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.

  21. 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.

  22. 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.

  23. 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.

  24. 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.

  25. 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.

  26. 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.

  27. 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.

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

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

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

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

  32. 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.

Some slides from talks

  1. A logical approach to TFNP (pdf)
    Reflections on Propositional Proofs in Algorithms and Complexity, Workshop at FOCS 21, online, 7 February 2022.

  2. DRAT proofs, propagation redundancy and extended resolution (pdf)
    SAT 2019, Calouste Gulbenkian Foundation, Lisbon, 9 July 2019.

  3. Approximate counting and NP search (pdf)
    ITI fest, Villa Lanna, Prague, 4 December 2018.

  4. Random resolution (pdf)
    Proof Complexity and Beyond, MF Oberwolfach, 18 August 2017.

  5. Small circuits for feasible set functions (pdf)
    Prague–Vienna Set Theory Workshop, Czech Academy of Sciences, 17 October 2016.

  6. A feasible set theory (pdf)
    Journées sur les Arithmétiques Faibles 35, University of Lisbon, 6 June 2016.

  7. Parity games and propositional proofs (pdf)
    Proof Complexity 2014, Vienna Technical University, 13 August 2014.

Other things

9/10/21 Neil Thapen