Humboldt-Universität zu Berlin - Faculty of Mathematics and Natural Sciences - Theoretical Computer Science

Logic in Computer Science

 

Prof. Dr. Nicole Schweikardt

Professor for Theoretical Computer Science

Prof. Dr. Christoph Berkholz

Junior professor for Logic and Complexity

 

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

 

News:

  • 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.
  • The paper "Counting Homomorphisms from Hypergraphs of Bounded Generalised Hypertree Width: A Logical Characterisation" by Benjamin Scheidt and Nicole Schweikardt was accepted at MFCS 2023.
  • The paper "A dichotomy for succinct representations of homomorphisms" by Christoph Berkholz and Harry Vinall-Smeeth was accepted at ICALP 2023.
  • The paper "Puzzling over Subsequence-Query Extensions: Disjunction and Generalised Gaps" by André Frochaux and Sarah Kleest-Meißner was accepted at AMW 2023.
  • The paper "Simulating Logspace-Recursion with Logarithmic Quantifier Depth" by Steffen van Bergerem, Martin Grohe, Sandra Kiefer, and Luca Oeljeklaus was accepted at LICS 2023.
  • The paper "Discovering Multi-Dimensional Event Queries from Traces - From Theory to Practice" by Sarah Kleest-Meißner, Rebecca Sattler, Markus Schmid, Nicole Schweikardt and Matthias Weidlich was accepted at BTW'23.
  • The paper "Subsequences With Gap Constraints: Complexity Bounds for Matching and Analysis Problems" by Joel D. Day, Maria Kosche, Florin Manea and Markus Schmid was accepted at ISAAC 2022.
  • On 01.08.2022 Prof. Dr. Christoph Berkholz began leading the Algorithms group at the Institute for Theoretical Computer Science, TU Ilmenau.
  • The paper "Enumeration for FO Queries over Nowhere Dense Graphs" by Nicole Schweikardt, Luc Segoufin and Alexandre Vigny was accepted by the Journal of the ACM.