Parameterised Counting Constraint Satisfaction Problems via Holants on Hypergraphs
Panagiotis Aivasiliotis, Andreas Göbel, Marc Roth · 2025
Read Parameterised Counting Constraint Satisfaction Problems via Holants on Hypergraphs by Panagiotis Aivasiliotis, Andreas Göbel, Marc Roth (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-19794.txt.
Introduction
Panagiotis Aivasiliotis, Andreas Göbel, and Marc Roth classify, in 2025 work, how hard a broad family of counting tasks is. The tasks ask how many ways a set number of switches can be set so all rules hold. Past work had fenced itself to narrow cases, such as maps between set forms or fixed rule tongues.
Their frame allows rule tongues of any size, which lets it hold tasks the old frames missed, like weighted choice tasks on web-like graphs and counts of neat sums' roots. They recast the tasks in a web-count frame and prove full split laws: for each such task the work is either light or provably hard, on two scales. New graph tricks and basis tools carry the proof.
Catalog record
| CREATOR | Panagiotis Aivasiliotis, Andreas Göbel, Marc Roth |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 173 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-19794