Graph Homomorphisms with Complex Values: A Dichotomy Theorem

DOI10.1007/978-3-642-14165-2_24zbMath1288.05178OpenAlexW2005716876MaRDI 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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (13)

Complexity of correspondence \(H\)-colourings ⋮ The complexity of complex weighted Boolean \#CSP ⋮ The complexity of weighted and unweighted \(\#\)CSP ⋮ The Ising partition function: zeros and deterministic approximation ⋮ Progress in Complexity of Counting Problems ⋮ Lee-Yang theorems and the complexity of computing averages ⋮ Spin systems on \(k\)-regular graphs with complex edge functions ⋮ A computational proof of complexity of some restricted counting problems ⋮ Unnamed Item ⋮ Zero-free regions of partition functions with applications to algorithms and graph limits ⋮ The Complexity of Symmetric Boolean Parity Holant Problems ⋮ The complexity of counting homomorphisms to cactus graphs modulo 2 ⋮ Approximate Counting via Correlation Decay in Spin Systems

This page was built for publication: Graph Homomorphisms with Complex Values: A Dichotomy Theorem