Adjoint Homomorphism Counting Workshop (ad hoc)
10 July 2023, adjoint with ICALP 2023


In recent years, the study of homomorphism counting resurged in various subfields within theoretical computer science. For example, from a complexity theoretic point of view, it was shown that counting problems from different domains can be understood by expressing them as linear combinations of homomorphism counts. Such linear combinations enjoy the exceptional and very useful "monotonicity property" of being exactly as hard to compute as their hardest terms. Since the complexity of computing the individual terms, i.e., of counting homomorphisms, is reasonably well understood, this strategy allowed the community to make significant progress in the study of the complexity of various counting problems arising in database theory and network sciences.

From a more abstract perspective, the numbers of homomorphisms between graphs encode valuable information. For example, a classical result by Lovász shows that homomorphism counts from all graphs into a given graph G identify G up to isomorphism. Restricting the class of graphs from which homomorphisms are counted yields natural relaxations of graph isomorphism that are connected to the expressiveness of logics. Furthermore, in pure mathematics, homomorphism counts enable a definition of convergent graph sequences that leads to so-called graph limits, which are an active area of study.

The purpose of this workshop is two-fold, namely,

  • to provide a forum for researchers whose work already relates to homomorphism counts, with the goal of translating results between different domains and finding common grounds for collaborations, and

  • to invite others with a background/interest in algorithms and complexity, logic, graph theory, and/or combinatorics to the theory and applications of homomorphism counts.

Confirmed Invited Speakers

  • Lior Gishboliner, ETH Zurich

  • Martin Grohe, University of Aachen

  • Daniel Král, Masaryk University Brno

  • Laura Mančinska, University of Copenhagen

  • Stefan Mengel, CNRS, CRIL, Lens

  • David E. Roberson, Technical Univ. of Denmark


Radu Curticapean, IT University of Copenhagen

Marc Roth , University of Oxford

Location and Schedule

July 10, 2023 in Paderborn, Germany
on-site, but virtual participation possible in exceptional cases

9:00 - 18:00
final schedule TBA


For planning purposes, please indicate (non-binding) interest in the provided form.

Official registration will likely occur in conjunction with the ICALP registration.