Curriculum Vitae

Name	Emil Jeřábek
Date of birth	27 June 1977
Place of birth	Prague, Czechoslovakia
Address	Institute of Mathematics, Czech Academy of Sciences Žitná 25 115 67  Praha 1 Czech Republic +420 222 090 772 jerabek@math.cas.skip-this-part.cz https://users.math.cas.cz/~jerabek/
ORCID iD	0000-0002-9057-3413

Education

2001–2005	Postgraduate student at the Faculty of Mathematics and Physics of the Charles University, Prague Supervisor: Jan Krajíček (Institute of Mathematics, Czech Academy of Sciences) Ph.D. degree obtained June 2005
1995–2002	Undergraduate student at the Faculty of Arts of the Charles University, Prague Master’s degree (Mgr) obtained February 2002
1995–2001	Undergraduate student at the Faculty of Mathematics and Physics of the Charles University, Prague Master’s degree (Mgr) obtained May 2001

Employment

since Oct 2006	Full-time position at the Institute of Mathematics of the Czech Academy of Sciences
Oct 2005–Oct 2006	Postdoc position at the Department of Computer Science of the University of Toronto
Mar–Aug 2005	Postdoc position at the Department of Philosophy of the University of Utrecht
2003–2005	Graduate student position at the Institute of Mathematics of the Czech Academy of Sciences
1999–2009	Part-time position at the Faculty of Mathematics and Physics of the Charles University

Awards

2022	Research Professor (DSc.) degree
2016	Neuron Award for Promising Young Scientists
2010	Otto Wichterle Award

Teaching

2022–present	Faculty of Mathematics and Physics of the Charles University (Mathematical Logic, Introduction to Mathematical Logic)
2007–2011 (intermittently)	Faculty of Arts of the Charles University (Set Theory, Model Theory)

Professional activities

• Member of programme committees of the conferences Advances in Modal Logic (AiML) 2024, Czech Gathering of Logicians 2023, Logic Colloquium 2022, Czech Gathering of Logicians 2022, AiML 2018, International Workshop on Unification (UNIF) 2018, and Computability in Europe (CiE) 2017. Member of the organizing committee of Prague Gathering of Logicians (PGL) 2016. Programme committee chair of PGL 2015. Co-editor of the proceedings of the International Tbilisi Symposium on Logic, Language, and Computation (TbiLLC) 2013.
• Reviewer for the zbMATH Open (formerly Zentralblatt MATH) database.
• Principal investigator of project Complexity of Mathematical Proofs and Structures, 2019–21, GA ČR GA19-05497S.
  Co-investigator of project Dynamic Formal Systems, 2007–10, GA AV ČR IAA900090703.
• Team member of projects:
  Logic and Unsatisfiability, 2023–25, GA ČR GA23-04825S, principal investigator N. Thapen.
  Feasibility, Logic and Randomness in Computational Complexity (FEALORA), 2014–18, ERC 339691, principal investigator P. Pudlák.
  Center of Excellence – Institute for Theoretical Computer Science (CE-ITI), 2012–18, GA ČR GBP202/12/G061, principal investigator J. Nešetřil.
  Mathematical Logic, Complexity, and Algorithms, 2009–13, GA AV ČR IAA100190902, principal investigator J. Sgall.
  Institute for Theoretical Computer Science (ITI), 2005–11, MŠMT ČR 1M0545, principal investigator J. Nešetřil.
  Theories, Proofs and Computational Complexity, 2004–08, GA AV ČR IAA1019401, principal investigator P. Pudlák.
• Regular contributor on MathOverflow and Theoretical Computer Science Stack Exchange.

Conference and workshop talks

Invited talks

• Canonical rules, Derivation Rules and Unification (International Workshop on Modal Logic IWML06), Istanbul, June 2006.
• Approximate counting in bounded arithmetic, 29es Journées sur les Arithmétiques Faibles (JAF29), Warsaw, June 2010.
• Rules with parameters in modal logic, The 26th International Workshop on Unification (UNIF), Manchester, July 2012.
• Admissibility and unification with parameters, Logic, Algebra and Truth Degrees (LATD), Kanazawa, September 2012.
• Bounded arithmetic (tutorial), Black Box Groups and Model Theory, Manchester, September 2013.
• Open induction in a TC⁰ arithmetic, Prague Gathering of Logicians, Prague, February 2014.
• Generalizing the clone–coclone Galois connection, Topology, Algebra, and Categories in Logic, Ischia, June 2015.
• Diophantine formulas, Journées sur les Arithmétiques Faibles (JAF35), Lisbon, June 2016.
• Counting in weak theories, Logic Colloquium, Stockholm, August 2017.
• Galois connection for multiple-output operations, Arbeitstagung Allgemeine Algebra (AAA96), Darmstadt, June 2018.
• Factoring and bounded arithmetic, Symposium on 50 Years of Complexity Theory: A Celebration of the Work of Stephen Cook, Toronto, May 2019.
• Admissible rules and their complexity, 24th Applications of Logic in Philosophy and the Foundations of Mathematics, Szklarska Poręba, May 2019.
• Hereditarily bounded sets, Online International Workshop on Gödel’s Incompleteness Theorems, August 2021.
• Disjunction-free disjunction property, Computability in Europe, Batumi, July 2023.

Other talks

• A note on Grzegorczyk’s logic, Logic Colloquium (LC2003), Helsinki, August 2003.
• Bounded arithmetic in 3-valued logic, Logic Colloquium (LC2004), Torino, July 2004.
• Hardness amplification in bounded arithmetic, 24èmes Journées d’Arithmétique Faible (JAF24), Fontainebleau, May 2005.
• Approximate counting in bounded arithmetic, New Directions in Proof Complexity, Cambridge, April 2006.
• Proof systems for modal logics, Logic Colloquium (LC2007), Wrocław, July 2007.
• Admissible rules of Łukasiewicz logic, Logic Colloquium (LC2009), Sofia, July 2009.
• On monotone sequent calculus, Barriers in Computational Complexity, Princeton, August 2009.
• Weak pigeonhole principle and approximate counting, Ramsey Theory in Logic, Combinatorics and Complexity (RaTLoCC), Bertinoro, October 2009.
• Proofs with monotone cuts, Logic Colloquium (LC2010), Paris, July 2010.
• Admissible rules and Łukasiewicz logic, Algebraic Semantics for Uncertainty and Vagueness, Salerno, May 2011.
• Admissible rules and Łukasiewicz logic, Workshop on Admissible Rules and Unification, Utrecht, May 2011.
• Root finding in TC⁰, Proof complexity, Banff, October 2011.
• Root finding in TC⁰ and open induction, Logical Approaches to Barriers in Complexity II, Cambridge, March 2012.
• Logics with directed unification, Algebra and Coalgebra meet Proof Theory (ALCOP), Utrecht, April 2013.
• Open induction in a TC⁰ arithmetic, Logic Colloquium, Évora, July 2013.
• Complexity of unification and admissibility with parameters in transitive modal logics, 10th International Tbilisi Symposium on Language, Logic and Computation (TbiLLC), Gudauri, September 2013.
• Parameter-free induction in bounded arithmetic, Proof Complexity, Vienna, July 2014.
• Recursive functions vs. classification theory, Utrecht Workshop on Proof Theory, April 2015.
• Fragments of intuitionistic logic and proof complexity, Logic, Algebra, and Truth Degrees (LATD), Phalaborwa, June 2016.
• Parameter-free bounded induction, Proof Complexity, Dagstuhl, February 2018.
• Bounded induction without parameters, FEALORA Farewell Workshop, Špindlerův Mlýn, November 2018.
• Reflection principles in weak and strong arithmetics, Logic Colloquium, Prague, August 2019.
• Hereditarily bounded sets, Complexity Theory with a Human Face, 2nd Edition, Špindlerův Mlýn, October 2021.
• Iterated multiplication in VTC⁰, 40ème Journées sur les Arithmétiques Faibles (JAF40), Athens, October 2021.
• Elementary analytic functions in VTC⁰, Czech Gathering of Logicians, Prague, June 2022.
• Elementary analytic functions in VTC⁰, Complexity Theory with a Human Face, 3rd Edition, Špindlerův Mlýn, June 2022.
• Elementary analytic functions in VTC⁰, Mathematical Approaches to Lower Bounds: Complexity of Proofs and Computation, Edinburgh, July 2022.
• On the complexity of addition, Czech Gathering of Logicians, Ostrava, June 2023.

Publications

Research papers

1. A note on Grzegorczyk’s logic, Mathematical Logic Quarterly 50 (2004), no. 3, pp. 295–296.
2. Dual weak pigeonhole principle, Boolean complexity, and derandomization, Annals of Pure and Applied Logic 129 (2004), pp. 1–37.
3. Admissible rules of modal logics, Journal of Logic and Computation 15 (2005), no. 4, pp. 411–431.
4. 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.
5. Frege systems for extensible modal logics, Annals of Pure and Applied Logic 142 (2006), pp. 366–379.
6. The strength of sharply bounded induction, Mathematical Logic Quarterly 52 (2006), no. 6, pp. 613–624.
7. Complexity of admissible rules, Archive for Mathematical Logic 46 (2007), no. 2, pp. 73–92.
8. On independence of variants of the weak pigeonhole principle, Journal of Logic and Computation 17 (2007), no. 3, pp. 587–604.
9. with Michal Rössler: Fragment of nonstandard analysis with a finitary consistency proof, Bulletin of Symbolic Logic 13 (2007), no. 1, pp. 54–70.
10. Approximate counting in bounded arithmetic, Journal of Symbolic Logic 72 (2007), no. 3, pp. 959–993.
11. Independent bases of admissible rules, Logic Journal of the IGPL 16 (2008), no. 3, pp. 249–267.
12. Proof complexity of the cut-free calculus of structures, Journal of Logic and Computation 19 (2009), no. 2, pp. 323–339.
13. 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.
14. Approximate counting by hashing in bounded arithmetic, Journal of Symbolic Logic 74 (2009), no. 3, pp. 829–860.
15. Canonical rules, Journal of Symbolic Logic 74 (2009), no. 4, pp. 1171–1205.
16. Abelian groups and quadratic residues in weak arithmetic, Mathematical Logic Quarterly 56 (2010), no. 3, pp. 262–278.
17. Admissible rules of Łukasiewicz logic, Journal of Logic and Computation 20 (2010), no. 2, pp. 425–447.
18. Bases of admissible rules of Łukasiewicz logic, Journal of Logic and Computation 20 (2010), no. 6, pp. 1149–1163.
19. On theories of bounded arithmetic for NC¹, Annals of Pure and Applied Logic 162 (2011), no. 4, pp. 322–340.
20. A sorting network in bounded arithmetic, Annals of Pure and Applied Logic 162 (2011), no. 4, pp. 341–355.
21. with Phuong Nguyen: Simulating non-prenex cuts in quantified propositional calculus, Mathematical Logic Quarterly 57 (2011), no. 5, pp. 524–532.
22. Proofs with monotone cuts, Mathematical Logic Quarterly 58 (2012), no. 3, pp. 177–187.
23. Sequence encoding without induction, Mathematical Logic Quarterly 58 (2012), no. 3, pp. 244–248.
24. Root finding with threshold circuits, Theoretical Computer Science 462 (2012), pp. 59–69.
25. The ubiquity of conservative translations, Review of Symbolic Logic 5 (2012), no. 4, pp. 666–678.
26. with Leszek Kołodziejczyk: Real closures of models of weak arithmetic, Archive for Mathematical Logic 52 (2013), no. 1–2, pp. 143–157.
27. The complexity of admissible rules of Łukasiewicz logic, Journal of Logic and Computation 23 (2013), no. 3, pp. 693–705.
28. 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.
29. Open induction in a bounded arithmetic for TC⁰, Archive for Mathematical Logic 54 (2015), no. 3–4, pp. 359–394.
30. Rules with parameters in modal logic I, Annals of Pure and Applied Logic 166 (2015), no. 9, pp. 881–933.
31. Blending margins: The modal logic K has nullary unification type, Journal of Logic and Computation 25 (2015), no. 5, pp. 1231–1240.
32. Integer factoring and modular square roots, Journal of Computer and System Sciences 82 (2016), no. 2, pp. 380–394.
33. A note on the substructural hierarchy, Mathematical Logic Quarterly 62 (2016), no. 1–2, pp. 102–110.
34. Division by zero, Archive for Mathematical Logic 55 (2016), no. 7, pp. 997–1013.
35. Cluster expansion and the boxdot conjecture, Mathematical Logic Quarterly 62 (2016), no. 6, pp. 608–614.
36. Proof complexity of intuitionistic implicational formulas, Annals of Pure and Applied Logic 168 (2017), no. 1, pp. 150–190.
37. Galois connection for multiple-output operations, Algebra Universalis 79 (2018), article no. 17, 37 pp.
38. Rigid models of Presburger arithmetic, Mathematical Logic Quarterly 65 (2019), no. 1, pp. 108–115.
39. Induction rules in bounded arithmetic, Archive for Mathematical Logic 59 (2020), no. 3, pp. 461–501.
40. Recursive functions and existentially closed structures, Journal of Mathematical Logic 20 (2020), no. 1, article no. 2050002, 52 pp.
41. Rules with parameters in modal logic II, Annals of Pure and Applied Logic 171 (2020), no. 10, article no. 102829, 59 pp.
42. On the complexity of the clone membership problem, Theory of Computing Systems 65 (2021), no. 5, pp. 839–868.
43. The theory of hereditarily bounded sets, Mathematical Logic Quarterly 68 (2022), no. 2, pp. 243–256.
44. Iterated multiplication in VTC⁰, Archive for Mathematical Logic 61 (2022), no. 5–6, pp. 705–767.
45. On the proof complexity of logics of bounded branching, Annals of Pure and Applied Logic 174 (2023), no. 1, article no. 103181, 54 pp.
46. Elementary analytic functions in VTC⁰, Annals of Pure and Applied Logic 174 (2023), no. 6, article no. 103269, 50 pp.
47. Models of VTC⁰ as exponential integer parts, Mathematical Logic Quarterly 69 (2023), no. 2, pp. 244–260.

Theses

1. 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.
2. Provability logic of the Alternative Set Theory, Master’s thesis, Faculty of Philosophy and Arts, Charles University, Prague, 2001, 44 pp.
3. Weak pigeonhole principle, and randomized computation, Ph.D. thesis, Faculty of Mathematics and Physics, Charles University, Prague, 2005, 116 pp.
4. Bounded arithmetic and complexity, DSc. dissertation, Czech Academy of Sciences, Prague, 2021, 253 pp.

Edited volumes

1. Martin Aher, Daniel Hole, Emil Jeřábek, and Clemens Kupke (editors), Logic, Language, and Computation – 10th International Tbilisi Symposium on Logic, Language, and Computation, TbiLLC 2013, Gudauri, Georgia, September 23–27, 2013. Revised Selected Papers, Lecture Notes in Computer Science vol. 8984, Springer-Verlag, Berlin, Heidelberg, 2015, xiv+333 pp.