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

Description

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.

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