Gadgets and anti-gadgets leading to a complexity dichotomy

DOI10.1145/2090236.2090272zbMath1347.68178arXiv1108.3383OpenAlexW2074783224MaRDI QIDQ2826076

Jin-Yi Cai, Tyson Williams, Michael Kowalczyk

Publication date: 7 October 2016

Published in: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1108.3383

zbMATH Keywords

groupspin systemdichotomy theoremholographic algorithmholographic transformationgadget

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

The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems, Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits, Holographic algorithms beyond matchgates, A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory, A collapse theorem for holographic algorithms with matchgates on domain size at most 4, The complexity of planar Boolean \#CSP with complex weights, Unnamed Item

Cites Work

• Unnamed Item
• The reproducible properties of correct forecasts
• The dimensions of individual strings and sequences
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• The Complexity of Forecast Testing
• The Well-Calibrated Bayesian
• Asymptotic calibration
• Dimension in Complexity Classes
• Universal prediction
• THE FRACTIONAL DIMENSION OF A SET DEFINED BY DECIMAL PROPERTIES