News

Together with colleagues from HPI in Potsdam, Berlin, Marc Roth has a paper accepted at ICALP 2026 which takes place in London in 2026. This is the Flagship Conference of the European Association for Theoretical Computer Science recently promoted to A*, together with FOCS and STOC, one of the premiere venues for general Theoretical Computer Science.

This paper is the second of a two-part series (part 1 was in ICALP 2025) in which they investigated Holographic Algorithms in the context of fine-grained and parameterised complexity theory. Holographic Algorithms were invented by Les Valiant and are one of the most famous results of Valiant's program on counting complexity theory, which was one of the contributions for which he received the Turing Award. It has been known for a long time in the community that the classical tools for holographic algorithms do not work in the context of parameterised complexity theory. Their contribution in these papers is the development of a new methodology via the so-called homomorphism basis, which enabled us to fully solve the parameterised and fine-grained complexity of holographic algorithms for both graphs (Part 1) and Hypergraphs (Part 2).

Abstract
We study the complexity of the parameterised counting constraint satisfaction problem: given a set of constraints over a set of variables and a positive integer k, how many ways are there to assign k variables to 1 (and the others to 0) such that all constraints are satisfied. Existing work has so far exclusively focused on restricted settings such as finding and counting homomorphisms between relational structures due to Grohe (JACM 2007) and Dalmau and Jonsson (TCS 2004), or the case of finite constraint languages due to Creignou and Vollmer (SAT 2012), and Bulatov and Marx (SICOMP 2014).

In this work, we tackle a more general setting of Valued Parameterised Counting Constraint Satisfaction Problems (VCSPs) with infinite constraint languages. In this setting we are able to model significantly more general problems such as (weighted) parameterised factor problems on hypergraphs and counting weight-k solutions of systems of linear equations, not captured by existing complexity classifications.

We express parameterised VCSPs as parameterised Holant problems on uniform hypergraphs, and we establish complete and explicit complexity dichotomy theorems. For resolving the P vs. #P question, we mainly rely on hypergraph gadgets, the existence of which we prove using properties of degree sequences necessary for realisability in uniform hypergraphs. For the FPT vs. #W[1] question, we build upon the recently established combinatorial toolkit for parameterised holants on the special case of graphs by Aivasiliotis et al. (ICALP 2025) and also rely on an extension of the framework of the homomorphism basis due to Curticapean, Dell and Marx (STOC 17) to uniform hypergraphs. As a technical highlight, we also employ Curticapean's "CFI Filters'' (SODA 2024) to establish polynomial-time algorithms for isolating vectors in the homomorphism basis.

Reference
Panagiotis Aivasiliotis, Andreas Göbel, Marc Roth (2026), Symmetric Parameterised Holants on Hypergraphs: Towards a Classification for Parameterised VCSPs, ICALP 2026: International Colloquium on Automata, Languages and Programming DOI: 10.48550/arXiv.2508.19794