Dear all, this is a reminder for Martin Grohe's talk on Graph Representations Based on Homomorphisms <https://www.unravel.rwth-aachen.de/go/id/tazps?lidx=1#aaaaaaaaaatazrl> taking place *today at 16:30* in room 5053.2 and on Zoom. Please find the details below.
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).
Part of the programme of the research training group UnRAVeL is a series of introductory lectures on the topics of "randomness" and "uncertainty" in UnRAVeL’s research thrusts: Algorithms and complexity, verification, logic and languages, and their application scenarios. The main aim is to provide doctoral researchers as well as master students a broad overview of the subjects of UnRAVeL. Science undergoes continuous change and lives from the constant quest for novel and better results, which are presented at conferences and in journals. This year, 10 UnRAVeL professors will present some of their most recent research successes. Everyone interested, in particular doctoral researchers and master students, are invited to attend the UnRAVeL lecture series 2022 and engage in discussions with the researchers. The talks take place on Tuesdays, 16:30–18:00 in room 5053.2 in the ground floor of building E2. All events are hybrid. To join remotely, please use https://rwth.zoom.us/j/96003885007?pwd=aUczMVdVU0ZXVGtQUFpwQnJHQUFhUT09 / Meeting ID: 960 0388 5007 / Passcode: 273710 Please find a list of all upcoming talks on the UnRAVeL website <https://www.unravel.rwth-aachen.de/cms/UnRAVeL/Studium/~pzix/Ringvorlesung-Veranstaltung/?lidx=1> and below: * 10/05/2022 Martin Grohe: Graph Representations Based on Homomorphisms * 17/05/2022 Christina Büsing: A Branch & Bound Algorithm for Robust Binary Optimization with Budget Uncertainty * 24/05/2022 Erika Ábrahám: The Challenge of Compositionality for Stochastic Hybrid Systems * 21/06/2022 Sebastian Trimpe: Uncertainty Bounds for Gaussian Process Regression with Applications to Safe Control and Learning * 28/06/2022 Britta Peis: Stackelberg Network Pricing Games * 05/07/2022 Gerhard Lakemeyer: Tractable Reasoning in First-Order Knowledge Bases We are looking forward to seeing many of you in the UnRAVeL survey lecture "What's New in UnRAVeL?". Best regards, Tim Seppelt, Birgit Willms, and Andreas Klinger