Neil Thapen

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

• The complexity of proving that a graph is Ramsey (pdf)
  Massimo Lauria, Pavel Pudlák, Vojtěch Rödl and Neil Thapen. Submitted, 2013.
• Space Complexity in Polynomial Calculus (pdf)
  Yuval Filmus, Massimo Lauria, Jakob Nordström, Neil Thapen and Noga Ron-Zewi. IEEE Conference on Computational Complexity 2012, pages 334-344, 2012.
• Fragments of approximate counting (pdf)
  Sam Buss, Leszek Kołodziejczyk and Neil Thapen. Submitted, 2012.
• How much randomness is needed for statistics? (pdf)
  Bjørn Kjos-Hanssen, Antoine Taveneaux and Neil Thapen. Computability in Europe 2012, LNCS Vol 7318, pages 395-404, 2012.
• 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.
• 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.
• 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.
• 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.
• The polynomial and linear hierarchies in V0 (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.)
• 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.
• 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.
• 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.)
• A note on Delta_1 induction and Sigma_1 collection (pdf)
  Neil Thapen. Fundamenta Mathematicae, Vol 186, Pages 79-84, 2005.
• Resolution and pebbling games (pdf)
  Nicola Galesi and Neil Thapen. SAT 2005, LNCS 3569, pages 76-90, 2005.
• Weak theories of linear algebra (pdf)
  Neil Thapen and Michael Soltys. Archive for Mathematical Logic, Vol 44:2, pages 195-208, 2005.
• Structures interpretable in models of bounded arithmetic (pdf)
  Neil Thapen. Annals of Pure and Applied Logic, Vol 136:3, pages 247-266, 2005.
• 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

• Notes on switching lemmas (pdf)
  Manuscript, 2009.
• The weak pigeonhole principle in models of bounded arithmetic (pdf)
  Doctoral thesis, University of Oxford, 2002.
• Doodal (flash)
  Fractal doodling tool, 2013.
• Other software