Institute for Theoretical Computer Science
The research group for Theoretical Computer Science is dedicated to the investigation of questions related to the nature of computation and its complexity. The main focus points are constraint satisfaction problems, complexity theory, and algebraic and logical methods used for their study.
Announcements
The 84th Workshop on Algorithms and Complexity of the Gesellschaft Informatik is jointly organized by the research group on theoretical computer science and the institute for algorithms and complexity of TU Hamburg and will take place at TU Hamburg on March 6, 2023. More information can be found here.
Publications from members of the institute
2022
-
Smooth approximations and CSPs over finitely bounded homogeneous structures
37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2022)
Publisher DOI
2021
-
A proof of the algebraic tractability conjecture for monotone monadic SNP
SIAM Journal on Computing 50 (4) : (2021)
Publisher DOI -
ω-categorical structures avoiding height 1 identities
Transactions of the American Mathematical Society 374 (1): 327-350 (2021-01)
Publisher DOI -
CORES over RAMSEY STRUCTURES
Journal of Symbolic Logic 86 (1): 352-361 (2021-03)
Publisher DOI -
The Containment Problem for Unambiguous Register Automata and Unambiguous Timed Automata
Theory of Computing Systems 65 (4): 706-735 (2021-05)
Publisher DOI -
Constraint Satisfaction Problems over Finite Structures
36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2021)
Publisher DOI -
Smooth approximations and relational width collapses
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Publisher DOI -
New techniques for universality in unambiguous register automata
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Publisher DOI
2020
-
Extensions of unificationmodulo ACUI
Mathematical Structures in Computer Science 30 (6): 597-626 (2020-06-01)
Publisher DOI -
Hrushovski's encoding and ω-categorical CSP monsters
47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Publisher DOI
2019
-
The containment problem for unambiguous register automata
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Publisher DOI -
Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems)
Symposium on Logic in Computer Science (2019)
Publisher DOI
2018
-
Discrete temporal constraint satisfaction problems
Journal of the ACM 65 (2): 9 (2018-02)
Publisher DOI -
A dichotomy for first-order reducts of unary structures
Logical Methods in Computer Science 14 (2) : 13 (2018-05-22)
Publisher DOI -
A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP
33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2018)
Publisher DOI -
Classification transfer for qualitative reasoning problems
27th International Joint Conference on Artificial Intelligence (IJCAI 2018)
Publisher DOI -
The complexity of disjunctive linear diophantine constraints
43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Publisher DOI
2016
-
Distance constraint satisfaction problems
Information and Computation 247 : 87-105 (2016-04-01)
Publisher DOI -
Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction
31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2016)
Publisher DOI
2015
-
Constraint satisfaction problems over the integers with successor
42nd International Colloquium on Automata, Languages and Programming (ICALP 2015)
Publisher DOI