Leszek Aleksander Kolodziejczyk

Tin Lok Wong

J. Math. Log., August, 2024

The Strength of the Dominance Rule.

[BibT_eX]

[DOI]

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

2023

How Strong is Ramsey's Theorem if infinity can be Weak?

[BibT_eX]

[DOI]

Katarzyna W. Kowalik

J. Symb. Log., 2023

2022

Approximate counting and NP search problems.

[BibT_eX]

[DOI]

J. Math. Log., 2022

2021

Weaker cousins of Ramsey's theorem over a weak base theory.

[BibT_eX]

[DOI]

Marta Fiori-Carones

Katarzyna W. Kowalik

Ann. Pure Appl. Log., 2021

In Search of the First-Order Part of Ramsey's Theorem for Pairs.

[BibT_eX]

[DOI]

Proceedings of the Connecting with Computability, 2021

2020

New bounds on the strength of some restrictions of Hindman's Theorem.

[BibT_eX]

[DOI]

Lorenzo Carlucci

Francesco Lepore

Konrad Zdanowski

Comput., 2020

2019

The logical strength of Büchi's decidability theorem.

[BibT_eX]

[DOI]

Henryk Michalewski

Cécilia Pradic

Michal Skrzypczak

Log. Methods Comput. Sci., 2019

Polynomial calculus space and resolution width.

[BibT_eX]

[DOI]

Nicola Galesi

Electron. Colloquium Comput. Complex., 2019

2018

Some Subsystems of Constant-Depth Frege with Parity.

[BibT_eX]

[DOI]

Michal Garlík

ACM Trans. Comput. Log., 2018

2016

End-Extensions of Models of Weak Arithmetic from Complexity-Theoretic Containments.

[BibT_eX]

[DOI]

J. Symb. Log., 2016

How unprovable is Rabin's decidability theorem?

[BibT_eX]

[DOI]

Henryk Michalewski

Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, 2016

2015

Categorical characterizations of the natural numbers require primitive recursion.

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 2015

2014

Fragments of Approximate Counting.

[BibT_eX]

[DOI]

Samuel R. Buss

J. Symb. Log., 2014

Small Stone in Pool.

[BibT_eX]

[DOI]

Samuel R. Buss

Log. Methods Comput. Sci., 2014

2013

Solutions in XML data exchange.

[BibT_eX]

[DOI]

Mikolaj Bojanczyk

Filip Murlak

J. Comput. Syst. Sci., 2013

Real closures of models of weak arithmetic.

[BibT_eX]

[DOI]

Emil Jerábek

Arch. Math. Log., 2013

2012

Truth definitions without exponentiation and the Σ₁ collection scheme.

[BibT_eX]

[DOI]

Jeff B. Paris

J. Symb. Log., 2012

2011

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

[BibT_eX]

[DOI]

Phuong Nguyen

Ann. Pure Appl. Log., 2011

Independence results for variants of sharply bounded induction.

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 2011

2010

A note on the Sigma1 collection scheme and fragments of bounded arithmetic.

[BibT_eX]

[DOI]

Math. Log. Q., 2010

The strength of sharply bounded induction requires MSP.

[BibT_eX]

[DOI]

Sedki Boughattas

Ann. Pure Appl. Log., 2010

2009

The polynomial and linear time hierarchies in V0.

[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

Partial collapses of the Sigma1 complexity hierarchy in models for fragments of bounded arithmetic.

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 2007

The Polynomial and Linear Hierarchies in V0.

[BibT_eX]

[DOI]

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

2006

On the Herbrand notion of consistency for finitely axiomatizable fragments of bounded arithmetic theories.

[BibT_eX]

[DOI]

J. Symb. Log., 2006

2004

Well-behaved principles alternative to bounded induction.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2004

A finite model-theoretical proof of a property of bounded query classes within PH.

[BibT_eX]

[DOI]

J. Symb. Log., 2004

Truth definitions in finite models.

[BibT_eX]

[DOI]