Emil Jeřábek — publications

On the theory of exponential integer parts, preprint, 2024, 27 pp. [arXiv] [abstract] [PDF, PS] [BIB]
A note on the complexity of addition, preprint, 2023, 5 pp. [arXiv] [abstract] [PDF, PS] [BIB]
A simplified lower bound for implicational logic, preprint, 2023, 31 pp. [arXiv] [abstract] [PDF, PS] [BIB]
Models of VTC⁰ as exponential integer parts, Mathematical Logic Quarterly 69 (2023), no. 2, pp. 244–260. [DOI, arXiv] [abstract] [PDF, PS] [BIB]
Elementary analytic functions in VTC⁰, Annals of Pure and Applied Logic 174 (2023), no. 6, article no. 103269, 50 pp. [DOI, arXiv] [abstract] [PDF, PS] [BIB]
Bounded arithmetic and complexity, DSc. dissertation, Czech Academy of Sciences, Prague, 2021, 253 pp. [PDF, PS]
The theory of hereditarily bounded sets, Mathematical Logic Quarterly 68 (2022), no. 2, pp. 243–256. [DOI, arXiv] [abstract] [PDF, PS] [BIB]
Iterated multiplication in VTC⁰, Archive for Mathematical Logic 61 (2022), no. 5–6, pp. 705–767. [DOI, arXiv] [abstract] [PDF, PS] [BIB]
On the proof complexity of logics of bounded branching, Annals of Pure and Applied Logic 174 (2023), no. 1, article no. 103181, 54 pp. [DOI, arXiv] [abstract] [PDF, PS] [BIB]
On the complexity of the clone membership problem, Theory of Computing Systems 65 (2021), no. 5, pp. 839–868. [DOI, arXiv] [abstract] [PDF, PS] [BIB]
Rules with parameters in modal logic II, Annals of Pure and Applied Logic 171 (2020), no. 10, article no. 102829, 59 pp. [DOI, arXiv] [abstract] [PDF, PS] [BIB]
Induction rules in bounded arithmetic, Archive for Mathematical Logic 59 (2020), no. 3, pp. 461–501. [DOI, arXiv] [abstract] [PDF, PS] [BIB]
Rigid models of Presburger arithmetic, Mathematical Logic Quarterly 65 (2019), no. 1, pp. 108–115. [DOI, arXiv] [abstract] [PDF, PS] [BIB]
Recursive functions and existentially closed structures, Journal of Mathematical Logic 20 (2020), no. 1, article no. 2050002, 52 pp. [DOI, arXiv] [abstract] [PDF, PS] [BIB]
Galois connection for multiple-output operations, Algebra Universalis 79 (2018), article no. 17, 37 pp. [DOI, arXiv] [abstract] [PDF, PS] [BIB]
Division by zero, Archive for Mathematical Logic 55 (2016), no. 7, pp. 997–1013. [DOI, arXiv] [abstract] [PDF, PS] [BIB]
Proof complexity of intuitionistic implicational formulas, Annals of Pure and Applied Logic 168 (2017), no. 1, pp. 150–190. [DOI, arXiv] [abstract] [PDF, PS] [BIB]
A note on the substructural hierarchy, Mathematical Logic Quarterly 62 (2016), no. 1–2, pp. 102–110. [DOI, arXiv] [abstract] [PDF, PS] [BIB]
Open induction in a bounded arithmetic for TC⁰, Archive for Mathematical Logic 54 (2015), no. 3–4, pp. 359–394. [DOI, arXiv] [abstract] [PDF, PS] [BIB]
with Ali Sadegh Daghighi, Mohammad Golshani, and Joel David Hamkins: The foundation axiom and elementary self-embeddings of the universe, in: Infinity, Computability, and Metamathematics: Festschrift celebrating the 60th birthdays of Peter Koepke and Philip Welch (S. Geschke, B. Löwe, and P. Schlicht, eds.), College Publications, London, 2014, pp. 89–112. [arXiv] [abstract] [PDF, PS] [BIB]
Cluster expansion and the boxdot conjecture, Mathematical Logic Quarterly 62 (2016), no. 6, pp. 608–614. [DOI, arXiv] [abstract] [PDF, PS] [BIB]
Rules with parameters in modal logic I, Annals of Pure and Applied Logic 166 (2015), no. 9, pp. 881–933. [DOI, arXiv] [abstract] [PDF, PS] [BIB]
Integer factoring and modular square roots, Journal of Computer and System Sciences 82 (2016), no. 2, pp. 380–394. [DOI, arXiv] [abstract] [PDF, PS] [BIB]
Sequence encoding without induction, Mathematical Logic Quarterly 58 (2012), no. 3, pp. 244–248. [DOI, arXiv] [abstract] [PDF, PS] [BIB]
Root finding with threshold circuits, Theoretical Computer Science 462 (2012), pp. 59–69. [DOI, arXiv] [abstract] [PDF, PS] [BIB]
The complexity of admissible rules of Łukasiewicz logic, Journal of Logic and Computation 23 (2013), no. 3, pp. 693–705. [DOI, arXiv] [abstract] [PDF, PS] [BIB]
Blending margins: The modal logic K has nullary unification type, Journal of Logic and Computation 25 (2015), no. 5, pp. 1231–1240. [DOI, arXiv] [abstract] [PDF, PS] [BIB]
The ubiquity of conservative translations, Review of Symbolic Logic 5 (2012), no. 4, pp. 666–678. [DOI, arXiv] [abstract] [PDF, PS] [BIB]
with Leszek Kołodziejczyk: Real closures of models of weak arithmetic, Archive for Mathematical Logic 52 (2013), no. 1–2, pp. 143–157. [DOI] [abstract] [PDF, PS] [BIB]
with Phuong Nguyen: Simulating non-prenex cuts in quantified propositional calculus, Mathematical Logic Quarterly 57 (2011), no. 5, pp. 524–532. [DOI] [abstract] [PDF, PS] [BIB]
Proofs with monotone cuts, Mathematical Logic Quarterly 58 (2012), no. 3, pp. 177–187. [DOI] [abstract] [PDF, PS] [BIB]
Bases of admissible rules of Łukasiewicz logic, Journal of Logic and Computation 20 (2010), no. 6, pp. 1149–1163. [DOI] [abstract] [PDF, PS] [BIB]
Admissible rules of Łukasiewicz logic, Journal of Logic and Computation 20 (2010), no. 2, pp. 425–447. [DOI] [abstract] [PDF, PS] [BIB]
A sorting network in bounded arithmetic, Annals of Pure and Applied Logic 162 (2011), no. 4, pp. 341–355. [DOI] [abstract] [PDF, PS] [BIB]
On theories of bounded arithmetic for NC¹, Annals of Pure and Applied Logic 162 (2011), no. 4, pp. 322–340. [DOI] [abstract] [PDF, PS] [BIB]
Abelian groups and quadratic residues in weak arithmetic, Mathematical Logic Quarterly 56 (2010), no. 3, pp. 262–278. [DOI] [abstract] [PDF, PS] [BIB]
Canonical rules, Journal of Symbolic Logic 74 (2009), no. 4, pp. 1171–1205. [DOI] [abstract] [PDF, PS] [BIB]
Proof complexity of the cut-free calculus of structures, Journal of Logic and Computation 19 (2009), no. 2, pp. 323–339. [DOI] [abstract] [PDF, PS] [BIB]
Approximate counting by hashing in bounded arithmetic, Journal of Symbolic Logic 74 (2009), no. 3, pp. 829–860. [DOI] [abstract] [PDF, PS] [BIB]
Substitution Frege and extended Frege proof systems in non-classical logics, Annals of Pure and Applied Logic 159 (2009), no. 1–2, pp. 1–48. [DOI] [abstract] [PDF, PS] [BIB]
Independent bases of admissible rules, Logic Journal of the IGPL 16 (2008), no. 3, pp. 249–267. [DOI] [abstract] [PDF, PS] [BIB]
On independence of variants of the weak pigeonhole principle, Journal of Logic and Computation 17 (2007), no. 3, pp. 587–604. [DOI] [abstract] [PDF, PS] [BIB]
The strength of sharply bounded induction, Mathematical Logic Quarterly 52 (2006), no. 6, pp. 613–624. [DOI] [abstract] [PDF, PS] [BIB]
Approximate counting in bounded arithmetic, Journal of Symbolic Logic 72 (2007), no. 3, pp. 959–993. [DOI] [abstract] [PDF, PS] [BIB]
Frege systems for extensible modal logics, Annals of Pure and Applied Logic 142 (2006), pp. 366–379. [DOI] [abstract] [PDF, PS] [BIB]
Complexity of admissible rules, Archive for Mathematical Logic 46 (2007), no. 2, pp. 73–92. [DOI] [abstract] [PDF, PS] [BIB]
Admissible rules of modal logics, Journal of Logic and Computation 15 (2005), no. 4, pp. 411–431. [DOI] [abstract] [PDF, PS] [BIB]
Weak pigeonhole principle, and randomized computation, Ph.D. thesis, Faculty of Mathematics and Physics, Charles University, Prague, 2005, 116 pp. [abstract] [browsable PDF, printable PS] [BIB]
A note on Grzegorczyk’s logic, Mathematical Logic Quarterly 50 (2004), no. 3, pp. 295–296. [DOI] [abstract] [PDF, PS] [BIB]
Dual weak pigeonhole principle, Boolean complexity, and derandomization, Annals of Pure and Applied Logic 129 (2004), pp. 1–37. [DOI] [abstract] [PDF, PS] [BIB]
with Michal Rössler: Fragment of nonstandard analysis with a finitary consistency proof, Bulletin of Symbolic Logic 13 (2007), no. 1, pp. 54–70. [DOI] [abstract] [PDF] [BIB]
with Tomáš Kepka and David Stanovský: Subdirectly irreducible non-idempotent left symmetric left distributive groupoids, Discussiones Mathematicae – General Algebra and Applications 25 (2005), no. 2, pp. 235–257. [DOI] [abstract] [PDF] [BIB]
Reflexe v neregulárních univerzech (Elementary embeddings in non-wellfounded set theory), Master’s thesis, Faculty of Mathematics and Physics, Charles University, Prague, 2001, 41 pp., in Czech. [abstract] [PDF, PS] [BIB]
Provability logic of the Alternative Set Theory, Master’s thesis, Faculty of Philosophy and Arts, Charles University, Prague, 2001, 44 pp. [introduction] [PDF, PS] [BIB]

Publications and preprints