Neil Thapen

Prague logic seminar

Papers/preprints

• With Sam Buss and Leszek Kolodziejczyk, "Fragments of approximate counting", preprint, 2012 (pdf)
• With Bjørn Kjos-Hanssen and Antoine Taveneaux, "How much randomness is needed for statistics?", submitted, 2012 (pdf)
• "Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem", in Archive for Mathematical Logic, Vol 50:7-8, 2011, pages 665-680, (pdf)
• With Pavel Pudlák, "Alternating minima and maxima, Nash equilibria and Bounded Arithmetic" (revised 2010), to appear in Annals of Pure and Applied Logic, (pdf)
• With Leszek Kolodziejczyk and Phuong Nguyen, "The provably total NP search problems of weak second order bounded arithmetic" (revised October 2010), in Annals of Pure and Applied Logic, Vol 162:6, 2011, pages 419-446, (pdf)
• With Alan Skelley, "The provably total search problems of bounded arithmetic" (revised March 2010), in Proceedings of the London Mathematical Society, Vol 103:1, 2011, pages 106-138, (pdf)
• With Leszek Kolodziejczyk, "The polynomial and linear hierarchies in V0", in Mathematical Logic Quarterly, Vol 55:5, 2009, pages 509-514 (an earlier version appeared in Proceedings of CiE 2007, LNCS 4497) (pdf)
• With Leszek Kolodziejczyk, "The polynomial and linear hierarchies in models where the weak pigeonhole principle fails", in Journal of Symbolic Logic, Vol 73:2, 2008, pages 578-592, (pdf)
• With Jan Krajicek and Alan Skelley, "NP search problems in low fragments of bounded arithmetic" (revised September 2006), in Journal of Symbolic Logic, Vol 72:2, 2007 (postscript)
• With Steve Cook, "The replacement scheme in weak arithmetic", in ACM Transactions on Computational Logic, Vol 7:4, 2006 (postscript at TOCL)
• "A note on Delta_1 induction and Sigma_1 collection", in Fundamenta Mathematicae, Vol 186, 2005 (postscript)
• With Nicola Galesi, "Resolution and pebbling games", SAT 2005 (postscript)
• With Michael Soltys, "Weak theories of linear algebra", in Archive for Mathematical Logic, Vol 44:2, 2005 (postscript)
• "Structures interpretable in models of bounded arithmetic", in Annals of Pure and Applied Logic, Vol 135, 2005 (postscript)
• "A model-theoretic characterization of the weak pigeonhole principle", in Annals of Pure and Applied Logic, Vol 118, 2002 (postscript , dvi)

Miscellaneous

• "Notes on switching lemmas", manuscript, 2009 (pdf)
• "The weak pigeonhole principle in models of bounded arithmetic", doctoral thesis, University of Oxford, 2002 (postscript, dvi)