Graph Homomorphisms with Complex Values: A Dichotomy Theorem
From MaRDI portal
Publication:5901171
DOI10.1007/978-3-642-14165-2_24zbMath1288.05178MaRDI QIDQ5901171
Jin-Yi Cai, Pinyan Lu, Xi Chen
Publication date: 7 September 2010
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-14165-2_24
68Q25: Analysis of algorithms and problem complexity
05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)
05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Related Items
Unnamed Item, The Complexity of Symmetric Boolean Parity Holant Problems, Approximate Counting via Correlation Decay in Spin Systems, The complexity of complex weighted Boolean \#CSP, The complexity of weighted and unweighted \(\#\)CSP, A computational proof of complexity of some restricted counting problems, Spin systems on \(k\)-regular graphs with complex edge functions, The Ising partition function: zeros and deterministic approximation, Zero-free regions of partition functions with applications to algorithms and graph limits, Complexity of correspondence \(H\)-colourings, Lee-Yang theorems and the complexity of computing averages, The complexity of counting homomorphisms to cactus graphs modulo 2, Progress in Complexity of Counting Problems
