Homomorphism Indistinguishability: Characterisations, Closure, Complexity

Add to your list(s) Download to your calendar using vCal

• Tim Seppelt (RWTH Aachen University)
• Tuesday 15 October 2024, 14:00-15:00
• Computer Laboratory, William Gates Building, Room SS03.

If you have a question about this talk, please contact Tom Gur.

In 1967, Lovász proved that two graphs G and H are isomorphic if and only if they are homomorphism indistinguishable over the the family of all graphs, i.e. for all graphs F the number of homomorphisms from F to G is equal to the number of homomorphisms from F to H. In recent years, many natural relaxations of graph isomorphism from fields as diverse as quantum information theory, algebraic graph theory, convex optimisation, or category theory have been characterised as homomorphism indistinguishability relations over restricted graph classes.

Motivated by the wealth of such results, we set out in this talk to develop a theory of homomorphism indistinguishability. We will focus on three themes:

- Characterisations: How to characterise homomorphism indistinguishability relations in particular in terms of systems of equations such as the Sherali—Adams or Lasserre integer programming hierarchies? - Closure: How to compare the expressiveness of homomorphism indistinguishability relations using tools from structural graph theory? - Complexity: What is the complexity of deciding whether two input graphs are homomorphism indistinguishable over a given graph class?

This talk is part of the Algorithms and Complexity Seminar series.

This talk is included in these lists:

• Algorithms and Complexity Seminar
• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory, William Gates Building, Room SS03
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• ki287

Note that ex-directory lists are not shown.