MSCA European Re-Integration Fellowship Project, 2021-2025

Principal investigator: Balder ten Cate (Associate Professor @ ILLC, University of Amsterdam)

This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement no 101031081.

Computational learning theory is a branch of computer science that studies the mathematical and algorithmic underpinnings of machine learning. It provides the concepts and methods to classify the computational feasibility of different learning problems. This project lies at the intersection of computational learning theory and logic, and it builds on recently identified new connections between learning theory and universal algebra. Its high-level goals are (i) to improve our understanding of learnability for fragments of first-order logic, motivated by applications in data management and knowledge representation, and (ii) to further develop and exploit the recently identified connections with universal algebra (as well as combinatorial graph theory, finite model theory, and fixed point logics), to developing a rich technical framework for proving new results. More concretely, we will study aspects of computational learning theory for fragments of first order logic under constraints (that is, in the presence of a background theory), with applications in data management and knowledge representation.

Publications:

  • B. ten Cate and T. Kappé. Algebras for Deterministic Computation are Inherently  Incomplete. Proceedings of POPL 2025 (to appear).
  • B. Bogaerts, B. ten Cate, B. McLean, and J. Van den Bussche (2024). Preservation theorems for Tarski’s relation algebra. Logical Methods in Computer Science 20(3): 20:1–20:17.
  • B. ten Cate and R. Koudijs (2024). Characterising Modal Formulas with Examples. ACM Transactions on Computational Logic 25(2): 12:1 – 12:27.
  • B. ten Cate, M. Funk, J. Ch. Jung, and C. Lutz (2024). On the Non-Efficient PAC Learnability of Conjunctive Queries. Information Processsing Letters 183: 106431.
  • B. ten Cate, R. Koudijs, and A. Ozaki (2024). On the Power and Limitations of Examples for Description Logic Concepts. Proceedings of IJCAI 2024.
  • B. ten Cate, V. Dalmau, and J. Opršal (2024). Right-Adjoints for Datalog Programs. Proceedings of ICDT 2024.
  • B. ten Cate, V. Dalmau, Ph. Kolaitis, W. Wu (2024). When do Homomorphism Counts Help in Query Algorithms? Proceedings of ICDT 2024.
  • B. ten Cate and J. Comer (2024). Craig Interpolation for Decidable First-Order Fragments. Proceedings of FOSSACS 2024. 🥇ETAPS Best Paper Nomination
  • B. ten Cate (2024). Craig Interpolation for Decidable Fragments of First-Order Logic. Proceedings of CSL 2024. 🥇Invited Lecture
  • B. ten Cate, R. Koudijs, and A. Ozaki (2024). On the Power and Limitations of Examples for Description Logic Concepts (Extended Abstract). Description Logic Workshop 2024.
  • B. ten Cate and A. Ganguly (2024). Characterizing Formulas via Post’s Lattice. Extended abstract presented at TACL 2024.
  • B. ten Cate, M. Funk, J. Ch. Jung, and C. Lutz (2023). Fitting Algorithms for Conjunctive Queries. SIGMOD Record 52(4): 6-18 (Database Principles column).🥇ACM SIGMOD Research Highlights Award Paper
  • B. ten Cate, M. Funk, J. Ch. Jung, and C. Lutz (2023). SAT-Based PAC Learning of Description Logic Concepts. Proceedings of IJCAI 2023. 🥇Distinguished Paper Award
  • B. ten Cate, V. Dalmau, M. Funk, and C. Lutz (2023). Extremal Fitting Problems for Conjunctive Queries. Proceedings of PODS 2023. 🥇Best Paper Award
  • B. ten Cate, M. Funk, J. Ch. Jung, and C. Lutz. (2023) SAT-Based PAC Learning of Description Logic Concepts (Extended Abstract). Description Logic Workshop 2023.
  • B. ten Cate, M. Funk, J. Ch. Jung, and C. Lutz (2023). Extremal Fitting CQs do not Generalize. Technical Report.
  • B. ten Cate and V. Dalmau (2022). Conjunctive Queries: Unique Characterizations and Exact Learnability. ACM Transactions on Database Systems 47(4): 14:1 – 14:41.
  • J. van Benthem, B. ten Cate, and R. Koudijs (2022). Local Dependence and Guarding. Proceedings of AIML 2022: 135-154.

Invited lectures:

  • Invited lecture, 2024 EACSL Annual Conference on Computer Science Logic 2024 (CSL’24)
  • Keynote lecture, 2023 Workshop on Interdisciplinary Research in Logic (IRL’23)
  • Distinguished Lecture, University of Bergen Department of Informatics (Nov 2023)
  • Invited lecture, Tbilisi Symposium on Language, Logic, and Computation (TbiLLC’23).

Other forms of dissemination (tutorials and event organization):

  • Summer school course: A modern introduction to Craig interpolation (5 day course at the ESSLLI 2024 Summer School with Frank Wolter).
  • Summer school course: Logic, Data Examples, and Learning (5 day course at the ESSLLI 2023 Summer School with Carsten Lutz)
  • Workshop organized: CIBD 2024, April 22-23, Amsterdam
  • Workshop organized: TbiLLC’23 workshop on learning and logic. Sep 21, 2023, Telavi (Georgia).
  • Workshop organized Joint KNAW/VvL webinar on causal reasoning and inference. Jan 24, 2023, online.
  • Workshop organized: Guarded Fragments: Current Trends and Applications (GF@25). Apr 5-6, 2022, online.

MSc thesis projects

  • Arun Ganguli (MSc Logic, UvA 2024): “Characterizing Formulas using Post’s Lattice“.
  • Jesse Comer (MSc Logic, UvA, 2023): “Homomorphism Counts, Database Queries, and Modal Logics”. 
  • Patrik Sestic (MSc Logic, UvA, 2023): “Unique Characterisability of Linear Temporal Logic“.
  • Valentino Filipetto (MSc Logic, UvA, 2022): “Constructing Queries from Data Examples”.
  • Raoul Koudijs (MSc Logic, UvA, 2022): “Learning Modal Formulas via Dualities”. 🥇 2022 VvL Master’s Thesis Prize.

Other academic service: