A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory
From MaRDI portal
Publication:4993265
DOI10.4230/LIPIcs.ITCS.2018.2zbMath1462.68078OpenAlexW2782633165MaRDI QIDQ4993265
Zhiguo Fu, Michael Kowalczyk, Kurt Girstmair, Jin-Yi Cai
Publication date: 15 June 2021
Full work available at URL: https://doi.org/10.4230/LIPIcs.ITCS.2018.2
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Miscellaneous applications of number theory (11Z05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Cites Work
- A dichotomy for real weighted Holant problems
- Holant problems for 3-regular graphs with complex edge functions
- The complexity of complex weighted Boolean \#CSP
- Spin systems on \(k\)-regular graphs with complex edge functions
- Character coordinates and annihilators of cyclotomic numbers
- The nonexistence of nontrivial linear relations between the roots of a certain irreducible equation
- Gadgets and anti-gadgets leading to a complexity dichotomy
- The statistics of dimers on a lattice
- Über die Hauptordnung der ganzen Elemente eines abelschen Zahlkörpers.
- Holographic Algorithms
- The Complexity of Weighted Boolean #CSP
- On the Structure of Polynomial Time Reducibility
- Holographic algorithm with matchgates is universal for planar #CSP over boolean domain
- A New Holant Dichotomy Inspired by Quantum Computation
- Dimer problem in statistical mechanics-an exact result
- The expressibility of functions on the boolean domain, with applications to counting CSPs
- The complexity of the counting constraint satisfaction problem
- Complexity of counting CSP with complex weights
- On a question of S. Chowla
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
