Matthias Lanzinger
| TISS: | Matthias Lanzinger |
| Room: | HD0305 |
| Phone: | +43/1/58801/1922-16 |
| Fax: | +43/1/58801/18493 |
| Email: |  |
Current interests
I am interested in a wide range of topics in theoretical computer science, database theory, and graph learning. I am currently particularly interested in the following areas, see the linked papers for details and full author lists.
Combined Complexity of Conjunctive Queries
When is conjunctive query evaluation polynomial-time tractable, and when does this coincide with fixed-parameter tractability?
WL, GNNs, and homomorphism counts
How can Weisfeiler-Leman, graph neural networks, and homomorphism counts be combined in new ways, especially beyond graphs?
- On the Power of the Weisfeiler-Leman Test for Graph Motif ParametersICLR 2024
- Homomorphism Counts for Graph Neural Networks: All About That BasisICML 2024
- Homomorphism Counts as Structural Encodings for Graph LearningICLR 2025
- Message Passing on the Edge: Towards Scalable and Expressive GNNsICML 2026
Decomposition parameters
Which structural width measures for hypergraphs admit useful algorithms?
- Complexity Analysis of Generalized and Fractional Hypertree DecompositionsJ. ACM 2021
- Fast Parallel Hypertree Decompositions in Logarithmic Recursion DepthPODS 2022 & ACM Trans. Database Syst.
- FPT Approximation of Generalised Hypertree Width for Bounded Intersection HypergraphsSTACS 2024 &ACM Trans. Comput. Theory
- FPT Parameterisations of Fractional and Generalised Hypertree WidthPODS 2026
- Soft and Constrained Hypertree WidthPODS 2025
Teaching
- 181.140 VU Database Theory (See also the course website)
- 184.780 VU Advanced Database Systems
Awards
- Dissertation Award of the City of Vienna.
- Best paper award DOLAP 2026, for Selective Use of Yannakakis' Algorithm for Consistent Performance Gains.
- Distinguished paper award PODS 2026, for >FPT Parameterisations of Fractional and Generalised Hypertree Width.
- Best paper award ICLP 2022, for MV-Datalog+-: Effective Rule-based Reasoning with Uncertain Observations.
Thesis Supervision
I am open to supervise student thesis in theoretical topics related to the areas described above.
If you're interested in conducting research under my guidance, please contact me for more information via email.
I generally do not supervise master's theses that are primarily focused on LLMs, surveys, or software engineering.