Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy

DOI10.1145/3305272zbMath1485.68104OpenAlexW2916507455MaRDI QIDQ5205792

Michael Kowalczyk, Tyson Williams, Jin-Yi Cai

Publication date: 16 December 2019

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3305272

zbMATH Keywords

interpolationpartition functioncounting complexityholographic algorithmsdichotomy theoremholant problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory ⋮ The computational complexity of Holant problems on 3-regular graphs ⋮ FKT is not universal -- a planar holant dichotomy for symmetric constraints

This page was built for publication: Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy