Neil Thapen

CoRR, April, 2025

2024

A Simple Supercritical Tradeoff between Size and Height in Resolution.

[BibT_eX]

[DOI]

Sam Buss

Electron. Colloquium Comput. Complex., 2024

How to fit large complexity classes into TFNP.

[BibT_eX]

[DOI]

CoRR, 2024

The Strength of the Dominance Rule.

[BibT_eX]

[DOI]

Proceedings of the 27th International Conference on Theory and Applications of Satisfiability Testing, 2024

TFNP Intersections Through the Lens of Feasible Disjunction.

[BibT_eX]

[DOI]

Pavel Hubácek

Erfan Khaniki

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

2022

Approximate counting and NP search problems.

[BibT_eX]

[DOI]

J. Math. Log., 2022

A separation of PLS from PPP.

[BibT_eX]

[DOI]

Ilario Bonacina

Electron. Colloquium Comput. Complex., 2022

Notes on switching lemmas.

[BibT_eX]

[DOI]

CoRR, 2022

2021

DRAT and Propagation Redundancy Proofs Without New Variables.

[BibT_eX]

[DOI]

Sam Buss

Log. Methods Comput. Sci., 2021

First-Order Reasoning and Efficient Semi-Algebraic Proofs.

[BibT_eX]

[DOI]

Fedor Part

Iddo Tzameret

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

2019

Feasible set functions have small circuits.

[BibT_eX]

[DOI]

Comput., 2019

DRAT Proofs, Propagation Redundancy, and Extended Resolution.

[BibT_eX]

[DOI]

Sam Buss

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

Polynomial Calculus Space and Resolution Width.

[BibT_eX]

[DOI]

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

On semantic cutting planes with very small coefficients.

[BibT_eX]

[DOI]

Massimo Lauria

Inf. Process. Lett., 2018

2017

Random Resolution Refutations.

[BibT_eX]

[DOI]

Proceedings of the 32nd Computational Complexity Conference, 2017

2016

A Tradeoff Between Length and Width in Resolution.

[BibT_eX]

[DOI]

Theory Comput., 2016

Cobham recursive set functions.

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 2016

2015

The Space Complexity of Cutting Planes Refutations.

[BibT_eX]

[DOI]

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

Fragments of Approximate Counting.

[BibT_eX]

[DOI]

Samuel R. Buss

J. Symb. Log., 2014

A trade-off between length and width in resolution.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Total Space in Resolution.

[BibT_eX]

[DOI]

Ilario Bonacina

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

The Ordering Principle in a Fragment of Approximate Counting.

[BibT_eX]

[DOI]

Albert Atserias

Electron. Colloquium Comput. Complex., 2013

Parity Games and Propositional Proofs.

[BibT_eX]

[DOI]

Arnold Beckmann

Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

The Complexity of Proving That a Graph Is Ramsey.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

Alternating minima and maxima, Nash equilibria and Bounded Arithmetic.

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 2012

Space Complexity in Polynomial Calculus.

[BibT_eX]

[DOI]

Proceedings of the 27th Conference on Computational Complexity, 2012

How Much Randomness Is Needed for Statistics?

[BibT_eX]

[DOI]

Bjørn Kjos-Hanssen

Antoine Taveneaux

Proceedings of the How the World Computes, 2012

2011

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

[BibT_eX]

[DOI]

Phuong Nguyen

Ann. Pure Appl. Log., 2011

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

[BibT_eX]

[DOI]

Arch. Math. Log., 2011

2009

The polynomial and linear time hierarchies in V<sup>0</sup>.

[BibT_eX]

[DOI]

Math. Log. Q., 2009

2008

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

[BibT_eX]

[DOI]

J. Symb. Log., 2008

2007

NP search problems in low fragments of bounded arithmetic.

[BibT_eX]

[DOI]

Jan Krajícek

Alan Skelley

J. Symb. Log., 2007

The Polynomial and Linear Hierarchies in V<sup>0</sup>.

[BibT_eX]

[DOI]

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

2005

Structures interpretable in models of bounded arithmetic.

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 2005

Weak theories of linear algebra.

[BibT_eX]

[DOI]

Michael Soltys

Arch. Math. Log., 2005

Resolution and Pebbling Games.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Satisfiability Testing, 2005

2004

The Strength of Replacement in Weak Arithmetic.

[BibT_eX]

[DOI]

Stephen A. Cook

Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS 2004), 2004

The Complexity of Treelike Systems over lamda-Local Formulae.

[BibT_eX]

[DOI]

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

2002

A model-theoretic characterization of the weak pigeonhold principle.

[BibT_eX]

[DOI]