Welcome to the web page of Emil Jeřábek^*

I am a researcher at the Department of Mathematical Logic and Theoretical Computer Science of the Institute of Mathematics of the Czech Academy of Sciences, with research interests in mathematical logic, including weak arithmetics and modal logic.

You can find me on the 2nd floor in the rear building of the Institute, office no. 522.

My CV. Some old stuff not related to my research.

Publications and preprints

• On the complexity of the clone membership problem, preprint, 2019, 24 pp. [arXiv] [abstract] [PDF, PS] [BIB]
• Rules with parameters in modal logic II, preprint, 2019, 67 pp. [arXiv] [abstract] [PDF, PS] [BIB]
• Induction rules in bounded arithmetic, preprint, 2018, 39 pp. [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, to appear. [DOI, arXiv] [abstract] [PDF, PS] [BIB]
• Galois connection for multiple-output operations, Algebra Universalis 79 (2018), article no. 17. [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]

Slides for talks

• Reflection principles in weak and strong arithmetics, Logic Colloquium, Prague, August 2019. [PDF, PS]
• Admissible rules and their complexity, 24th Applications of Logic in Philosophy and the Foundations of Mathematics, Szklarska Poręba, May 2019. [PDF, PS]
• Factoring and bounded arithmetic, Symposium on 50 Years of Complexity Theory: A Celebration of the Work of Stephen Cook, Toronto, May 2019. [PDF, PS]
• Bounded induction without parameters, FEALORA Farewell Workshop, Špindlerův Mlýn, November 2018. [PDF, PS]
• Counting in weak theories, Logic Colloquium, Stockholm, August 2017. [PDF, PS]
• Fragments of intuitionistic logic and proof complexity, Logic, Algebra, and Truth Degrees, Phalaborwa, June 2016. [PDF, PS]
• Diophantine formulas, Journées sur les Arithmétiques Faibles 35, Lisbon, June 2016. [PDF, PS]
• Generalizing the clone–coclone Galois connection, Topology, Algebra, and Categories in Logic, Ischia, June 2015. [PDF, PS]
• Recursive functions vs. classification theory, Utrecht Workshop on Proof Theory, April 2015. [PDF, PS]
• Parameter-free induction in bounded arithmetic, Proof Complexity, Vienna, July 2014. [PDF, PS]
• Complexity of unification and admissibility with parameters in transitive modal logics, 10th International Tbilisi Symposium on Language, Logic and Computation (TbiLLC), Gudauri, September 2013. [PDF, PS]
• Open induction in a TC⁰ arithmetic, Logic Colloquium, Évora, July 2013. [PDF, PS]
  An expanded version of the talk at the Prague Gathering of Logicians, February 2014: [PDF, PS]
• Logics with directed unification, Algebra and Coalgebra meet Proof Theory, Utrecht, April 2013. [PDF, PS]
• Admissibility and unification with parameters, Logic, Algebra, and Truth Degrees, Kanazawa, September 2012. [PDF, PS]
• Rules with parameters in modal logic, The 26th International Workshop on Unification (UNIF), Manchester, July 2012. [PDF, PS]
• Root finding in TC⁰ and open induction, Logical Approaches to Barriers in Complexity II, Cambridge, March 2012. [PDF, PS]
• Admissible rules and Łukasiewicz logic. This is a common unifier (not quite the mgu) of related talks presented at Algebraic Semantics for Uncertainty and Vagueness (Salerno, May 2011), Workshop on Admissible Rules and Unification (Utrecht, May 2011), and, in part, Logic Colloquium (Sofia, July 2009). [PDF, PS]
• Proofs with monotone cuts, Logic Colloquium, Paris, July 2010. [PDF, PS]
• Approximate counting in bounded arithmetic, 29es Journées sur les Arithmétiques Faibles, Warsaw, June 2010. [PDF, PS]
• On monotone sequent calculus, Barriers in Computational Complexity workshop, Princeton, August 2009. [PDF, PS]
• Proof systems for modal logics, Logic Colloquium, Wrocław, July 2007. [PDF, PS]
• Canonical rules, Derivation Rules and Unification (International Workshop on Modal Logic IWML06), İstanbul Kültür Üniversitesi, June 2006. [PDF, PS]
• Approximate counting in bounded arithmetic, New Directions in Proof Complexity, Cambridge, April 2006. [PDF, PS]

Links

• Prague Gathering of Logicians 2016