Logic in Computer Science

Welcome to the web presentation of the research groups "Theoretical Computer Science" and "Logic and Complexity"!

News:

• The papers “On the VC Dimension of First-Order Logic with Counting and Weight Aggregation” by Steffen van Bergerem and Nicole Schweikardt and “The Parameterized Complexity of Learning Monadic Second-Order Logic” by Steffen van Bergerem, Martin Grohe, and Nina Runde were accepted at CSL 2025.
• The paper “Learning Aggregate Queries Defined by First-Order Logic with Counting” by Steffen van Bergerem and Nicole Schweikardt was accepted at ICDT 2025.
• The paper “Subsequences With Generalised Gap Constraints: Upper and Lower Complexity Bounds” by Florin Manea, Jonas Richardsen, and Markus L. Schmid was accepted at CPM 2024.
• The paper “From Quantifier Depth to Quantifier Number: Separating Structures with k variables” by Harry Vinall-Smeeth was accepted at LICS 2024.
• The papers “On Homomorphism Indistinguishability and Hypertree Depth” by Benjamin Scheidt and “Verification of Population Protocols with Unordered Data” by Steffen van Bergerem, Roland Guttenberg, Sandra Kiefer, Corto Mascle, Nicolas Waldburger, and Chana Weil-Kennedy were accepted at ICALP 2024.
• The research project “Learning Aggregate Queries Described by Extensions of First-order Logic on Weighted Structures” was accepted to be funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation).
• The paper "Enumeration for MSO-Queries on Compressed Trees" by Markus Lohrey and Markus Schmid was accepted at PODS 2024.
• On 01.08.2022 Prof. Dr. Christoph Berkholz began leading the Algorithms group at the Institute for Theoretical Computer Science, TU Ilmenau.