Beyond Exact Counting: Approximation and Symmetry

This project lies in algorithms and computational complexity theory. It studies counting problems, which are linked to fundamental questions in complexity theory, with applications in network analysis, machine learning, probabilistic databases, and statistical physics. The proposed project is based on the observation that counting problems can be tackled using graph homomorphisms, which are certain structure-preserving maps between networks.

The project is related to the ERC Starting Grant "Counting (with) Homomorphisms", but it constitutes a separate project with complementary goals and synergies with the ERC project. While the ERC project is concerned with exact counting problems, the YI project focuses on approximate counting (which is closer to practical applications, where approximate counts often suffice) and the algebraic complexity of symmetric polynomials.

Specifically, in approximate counting, the project focuses on approximate counting of perfect matchings (certain global structures in networks), approximate counting of small patterns, and a general theory of approximate homomorphism counts, which can be used to define approximate similarity notions for networks. Regarding the algebraic complexity of symmetric polynomials, the project focuses on obtaining a full complexity-theoretic classification for a problem space of which previously only small fragments were classified.

During the short project period, it was shown that the main idea underlying the ERC Starting Grant can be generalized in an unexpected way from a parameterized reduction to a polynomial-time reduction. This paves the way to a more general study of counting problems, which was not possible with previous methods.