Survey Lecture: Martin Grohe: Graph Representations Based on Homomorphisms

Tuesday, May 10, 2022, 4:30pm

Location: Department of Computer Science, Ahornstr. 55, building E2 (no. 2356), ground floor, room: B-IT 5053.2.
We are looking forward to meeting you in person!
Nevertheless, all events are hybrid. To join remotely, please use:
Meeting ID: 960 0388 5007, Passcode: 273710

Speaker: Martin Grohe



Representations in terms of homomorphism counts provide a surprisingly rich view on graphs with applications ranging from logic to machine learning. Lovász (1967) showed that two graphs G and H are isomorphic if and only if they are homomorphism indistinguishable over the class of all graphs, i.e., for every graph F, the number of homomorphisms from F to G equals the number of homomorphisms from F to H. Recently, homomorphism indistinguishability over restricted classes of graphs such as bounded treewidth, bounded treedepth and planar graphs, has emerged as a surprisingly powerful framework for capturing diverse equivalence relations on graphs arising from logical equivalences and algebraic equation systems.

In this talk, I will introduce an algebraic framework for such results drawing from linear algebra and representation theory.

The talk is based on recent joint work with Gaurav Rattan and Tim Seppelt (to appear in ICALP 2022).