Publications of Leszek Kołodziejczyk
Research papers:
- L. A. Kołodziejczyk, N. Thapen, The strength of the dominance rule, arXiv:2406.13657. [PDF]. Conference version in proceedings of SAT 2024, 20:1-20:22.
- M. Fiori Carones, L. A. Kołodziejczyk, T. L. Wong, K. Yokoyama, An isomorphism theorem for models of Weak König's Lemma without primitive recursion, Journal of the European Mathematical Society, online first, 2024. [PDF]
- L. A. Kołodziejczyk, T. L. Wong, K. Yokoyama, Ramsey's theorem for pairs, collection, and proof size, Journal of Mathematical Logic, 24(2) (2024), paper no. 2350007. [PDF]
- L. A. Kołodziejczyk, K. W. Kowalik, K. Yokoyama, How strong is Ramsey's theorem if infinity can be weak?, Journal of Symbolic Logic, 88(2) (2023), 620-639. [PDF]
- L. A. Kołodziejczyk, N. Thapen, Approximate counting and NP search problems, Journal of Mathematical Logic 22(3) (2022), paper no. 2250012. [PDF]
- M. Fiori Carones, L. A. Kołodziejczyk, K. W. Kowalik, Weaker cousins of Ramsey's theorem over a weak base theory, Annals of Pure and Applied Logic 172(10) (2021), article 103028. [PDF]
- L. A. Kołodziejczyk, K. Yokoyama, Some upper bounds on ordinal-valued Ramsey numbers for colourings of pairs, Selecta Mathematica. New Series 26(4) (2020), paper 56. [PDF]
- L. Carlucci, L. A. Kołodziejczyk, F. Lepore, K. Zdanowski, New bounds on the strength of some restrictions of Hindman's Theorem, Computability 9(2) (2020), 139-153. [PDF]. Preliminary version in proceedings of CiE 2017.
- N. Galesi, L. A. Kołodziejczyk, N. Thapen, PCR space and resolution width, FOCS 2019, 1325-1337. [PDF]
- L. A. Kołodziejczyk, H. Michalewski, P. Pradic, M. Skrzypczak, The logical strength of Büchi's decidability theorem, Logical Methods in Computer Science 15(2) (2019), 16:1-16:31. [PDF]. Conference version in proceedings of CSL 2016.
- M. Garlík, L. A. Kołodziejczyk, Some subsystems of constant-depth Frege with parity, ACM Transactions on Computational Logic 19(4) (2018), article no. 29.
[PDF]
- L. A. Kołodziejczyk, H. Michalewski, How unprovable is Rabin's decidability theorem? [PDF]. Conference version in proceedings of LICS 2016, 788-797.
- L. A. Kołodziejczyk, End-extensions of models of weak arithmetic from complexity-theoretic containments, Journal of Symbolic Logic 81 (2016), 901-916. [PDF]
- L. A. Kołodziejczyk, K. Yokoyama, Categorical characterizations of the natural numbers require primitive recursion, Annals of Pure and Applied Logic 166 (2015), 219-231. [PDF]
- S. R. Buss, L. A. Kołodziejczyk, Small stone in pool, Logical Methods in Computer Science 10(2) (2014), paper 16. [PDF]
- S. R. Buss, L. A. Kołodziejczyk, K. Zdanowski, Collapsing modular counting in bounded arithmetic and constant depth propositional proofs, Transactions of the AMS 367 (2015), 7517-7563. [PDF]
- S. R. Buss, L. A. Kołodziejczyk, N. Thapen, Fragments of approximate counting, Journal of Symbolic Logic 79 (2014), 496-525. [PDF]
- E. Jeřábek, L. A. Kołodziejczyk, Real closures of models of weak arithmetic, Archive for Mathematical Logic 52 (2013), 143-157. [PDF]
- M. Bojańczyk, L. A. Kołodziejczyk, F. Murlak, Solutions in XML data exchange, Journal of Computer and System Sciences 79 (2013), 785-815. [PDF] Preliminary version in proceedings of ICDT 2011.
- Z. Adamowicz, L. A. Kołodziejczyk, J. Paris, Truth definitions without exponentiation and the Sigma_1 collection scheme, Journal of Symbolic Logic 77 (2012), 649-655. [PDF]
- L. A. Kołodziejczyk, Independence results for variants
of sharply bounded induction,
Annals of Pure and Applied Logic, 162 (2011), 981-990. [PDF]
- L. A. Kołodziejczyk, P. Nguyen, N. Thapen, The provably total NP search problems of weak second order bounded arithmetic, Annals of Pure and Applied Logic 162 (2011), 419-446. [PDF]
- Z. Adamowicz, L. A. Kołodziejczyk, A note on the Sigma_1 collection scheme and fragments of bounded arithmetic, Mathematical Logic Quarterly 56 (2010), 126-130. [PDF]
- S. Boughattas, L. A. Kołodziejczyk, The strength of sharply bounded induction requires MSP,
Annals of Pure and Applied Logic 161 (2010), 504-510. [PDF]
- L. A. Kołodziejczyk, N. Thapen, The polynomial and linear hierarchies in V^0,
Mathematical Logic Quarterly 55 (2009), 509-514. [PDF] Preliminary version
in proceedings of CiE 2007.
- L. A. Kołodziejczyk, N. Thapen, The polynomial and linear hierarchies in models where the weak pigeonhole principle fails, Journal of Symbolic Logic 73 (2008),
578-592. [PDF]
- Z. Adamowicz, L. A. Kołodziejczyk, Partial collapses of the Sigma_1 complexity hierarchy in models for fragments of bounded arithmetic, Annals of Pure and Applied Logic 145 (2007), 91-95. [PDF]
- L. A. Kołodziejczyk, On the Herbrand notion of consistency for finitely axiomatizable fragments of bounded arithmetic theories, Journal of Symbolic Logic 71 (2006), 624-638. [PDF]
- L. A. Kołodziejczyk, A finite model-theoretical proof of a property of bounded query classes within PH, Journal of Symbolic Logic 69 (2004), 1105-1116. [PDF]
- Z. Adamowicz, L. A. Kołodziejczyk, Well-behaved principles alternative to bounded induction, Theoretical Computer Science 322 (2004), 5-16. [PDF]
- L. A. Kołodziejczyk, Truth definitions in finite models, Journal of Symbolic Logic 69 (2004), 183-200. [PDF]
- Z. Adamowicz, L. A. Kołodziejczyk, P. Zbierski, An application of a reflection principle, Fundamenta Mathematicae 180 (2003), 139-159. [PDF]
Theses:
- Truth definitions and higher order logics in finite models, Ph.D. thesis, Institute of Philosophy, Warsaw University, 2005.
[PDF]
- Zasada kolekcji w arytmetyce [The collection principle in arithmetic],
master's thesis, Institute of Mathematics, Warsaw University, 2004.
- The expressive power of Henkin quantifiers with dualization, master's thesis, Institute of Philosophy, Warsaw University, 2002.
[PDF]
Varia:
- [po polsku, wspólnie z R. Szczepkowskim] przekład I księgi Elementów Euklidesa
[PDF]. Wstęp [PDF] i komentarz
[PDF]. Diagramy autorstwa Pawła Kośmickiego [PDF].
Całość ukazała się w Zagadnieniach Naukoznawstwa XLI(2) (2005), 269-336.
Strona główna