ERC Starting Grant · 2022
This project addresses the computational complexity of counting problems in graphs; such problems ask to compute the number of certain structures rather than merely deciding their existence. Counting problems find applications in diverse areas like network analysis, machine learning, probabilistic databases, and statistical physics. They are linked to fundamental questions in complexity theory and give rise to algorithmic breakthroughs for decision problems. The proposed project will go beyond the state of the art in computational counting by building bridges between algorithms/complexity and the mathematical theory of graph homomorphisms, which are structure-preserving maps between graphs.…
From the public funding record at EU CORDIS. Describes the funded project, not the reviews below.