Prof. Dr. Tobias Friedrich


Three Papers accepted at ICDT and AAAI

The International Conference on Database Theory (ICDT) is an established series of international conferences on research in the foundations and theory of data management. The 24th edition will be held in Nicosia, Cyprus, on March 23-26, 2021. The Algorithm Engineering group contributes one paper, where the authors give fine-grained lower bounds indicating that breadth first search in the product automaton is in many respects optimal for answering regular path queries on graph databases. These bounds are complemented with more sophisticated and efficient methods for particular types of queries, approximate solutions, or slightly superlinear preprocessing.

The 35th AAAI Conference on Artificial Intelligence (AAAI), a world-leading venue for research in artificial intelligence will be held virtually on February 2-9, 2021. The Algorithm Engineering group is contributing two papers to the 35th edition of this venue. The "Optimal Kidney Exchange with Immunosuppressants" paper augments a standard model of kidney exchange with the concept of "partially compatible" pairs, modeling the ability to bypass incompatibility constraints through drug interventions. The authors provide theory results analyzing computational aspects of the model, alongside experimental validation of their algorithms using empirical data. In the "Selfish Creation of Social Networks" paper, the authors propose and analyze a model for the creation of social networks by selfish agents. From the theoretical and empirical results of the paper, it can be seen that the proposed model is a promising step towards game-theoretic network creation models that describes networks featuring all core real-world properties.

  • Casel, Katrin; Schmid, Markus L.Fine-Grained Complexity of Regular Path Queries. International Conference on Database Theory (ICDT) 2021
  • Aziz, Haris; Cseh, Agnes; Dickerson, John; McElfresh, DuncanOptimal Kidney Exchange with Immunosuppressants. Conference on Artificial Intelligence (AAAI) 2021
  • Bilò, Davide; Friedrich, Tobias; Lenzner, Pascal; Lowski, Stefanie; Melnichenko, AnnaSelfish Creation of Social Networks. Conference on Artificial Intelligence (AAAI) 2021