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

CREATORPanagiotis Aivasiliotis, Andreas Göbel, Marc Roth
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE173 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-19794

Browse the full library · About the Tower of Babel