Neil Thapen

According to our database, Neil Thapen authored at least 36 papers between 2002 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of two.

2024

A Simple Supercritical Tradeoff between Size and Height in Resolution.

Sam Buss, Neil Thapen

Electron. Colloquium Comput. Complex., 2024

TFNP Intersections Through the Lens of Feasible Disjunction.

Pavel Hubácek, Erfan Khaniki, Neil Thapen

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2022

Approximate counting and NP search problems.

Leszek Aleksander Kolodziejczyk, Neil Thapen

J. Math. Log., 2022

A separation of PLS from PPP.

Ilario Bonacina, Neil Thapen

Electron. Colloquium Comput. Complex., 2022

Notes on switching lemmas.

Neil Thapen

CoRR, 2022

2021

DRAT and Propagation Redundancy Proofs Without New Variables.

Sam Buss, Neil Thapen

Log. Methods Comput. Sci., 2021

First-Order Reasoning and Efficient Semi-Algebraic Proofs.

Fedor Part, Neil Thapen, Iddo Tzameret

Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, 2021

2019

Polynomial calculus space and resolution width.

Nicola Galesi, Leszek Aleksander Kolodziejczyk, Neil Thapen

Electron. Colloquium Comput. Complex., 2019

Feasible set functions have small circuits.

Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller, Neil Thapen

Comput., 2019

Random resolution refutations.

Pavel Pudlák, Neil Thapen

Comput. Complex., 2019

DRAT Proofs, Propagation Redundancy, and Extended Resolution.

Sam Buss, Neil Thapen

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2019, 2019

2018

On semantic cutting planes with very small coefficients.

Massimo Lauria, Neil Thapen

Inf. Process. Lett., 2018

2017

The complexity of proving that a graph is Ramsey.

Massimo Lauria, Pavel Pudlák, Vojtech Rödl, Neil Thapen

Comb., 2017

2016

A Tradeoff Between Length and Width in Resolution.

Neil Thapen

Theory Comput., 2016

Cobham recursive set functions.

Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller, Neil Thapen

Ann. Pure Appl. Log., 2016

2014

Parity Games and Propositional Proofs.

Arnold Beckmann, Pavel Pudlák, Neil Thapen

ACM Trans. Comput. Log., 2014

The Ordering Principle in a Fragment of Approximate Counting.

Albert Atserias, Neil Thapen

ACM Trans. Comput. Log., 2014

Fragments of Approximate Counting.

Samuel R. Buss, Leszek Aleksander Kolodziejczyk, Neil Thapen

J. Symb. Log., 2014

A trade-off between length and width in resolution.

Neil Thapen

Electron. Colloquium Comput. Complex., 2014

The space complexity of cutting planes refutations.

Nicola Galesi, Pavel Pudlák, Neil Thapen

Electron. Colloquium Comput. Complex., 2014

Total space in resolution.

Ilario Bonacina, Nicola Galesi, Neil Thapen

Electron. Colloquium Comput. Complex., 2014

How much randomness is needed for statistics?

Bjørn Kjos-Hanssen, Antoine Taveneaux, Neil Thapen

Ann. Pure Appl. Log., 2014

2012

Space Complexity in Polynomial Calculus.

Yuval Filmus, Massimo Lauria, Jakob Nordström, Noga Ron-Zewi, Neil Thapen

Electron. Colloquium Comput. Complex., 2012

Alternating minima and maxima, Nash equilibria and Bounded Arithmetic.

Pavel Pudlák, Neil Thapen

Ann. Pure Appl. Log., 2012

2011

The provably total NP search problems of weak second order bounded arithmetic.

Leszek Aleksander Kolodziejczyk, Phuong Nguyen, Neil Thapen

Ann. Pure Appl. Log., 2011

Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem.

Neil Thapen

Arch. Math. Log., 2011

2009

The polynomial and linear time hierarchies in V⁰.

Leszek Aleksander Kolodziejczyk, Neil Thapen

Math. Log. Q., 2009

2008

The polynomial and linear hierarchies in models where the weak pigeonhole principle fails.

Leszek Aleksander Kolodziejczyk, Neil Thapen

J. Symb. Log., 2008

2007

NP search problems in low fragments of bounded arithmetic.

Jan Krajícek, Alan Skelley, Neil Thapen

J. Symb. Log., 2007

The Polynomial and Linear Hierarchies in V⁰.

Leszek Aleksander Kolodziejczyk, Neil Thapen

Proceedings of the Computation and Logic in the Real World, 2007

2006

The strength of replacement in weak arithmetic.

Stephen A. Cook, Neil Thapen

ACM Trans. Comput. Log., 2006

2005

Structures interpretable in models of bounded arithmetic.

Neil Thapen

Ann. Pure Appl. Log., 2005

Weak theories of linear algebra.

Neil Thapen, Michael Soltys

Arch. Math. Log., 2005

2004

Resolution and pebbling games

Nicola Galesi, Neil Thapen

Electron. Colloquium Comput. Complex., 2004

The Complexity of Treelike Systems over lamda-Local Formulae.

Nicola Galesi, Neil Thapen

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

2002

A model-theoretic characterization of the weak pigeonhold principle.

Neil Thapen

Ann. Pure Appl. Log., 2002