Holant Problems for Regular Graphs with Complex Edge Functions
arXiv:1001.0464
Abstract
We prove a complexity dichotomy theorem for Holant Problems on 3-regular graphs with an arbitrary complex-valued edge function. Three new techniques are introduced: (1) higher dimensional iterations in interpolation; (2) Eigenvalue Shifted Pairs, which allow us to prove that a pair of combinatorial gadgets in combination succeed in proving #P-hardness; and (3) algebraic symmetrization, which significantly lowers the symbolic complexity of the proof for computational complexity. With holographic reductions the classification theorem also applies to problems beyond the basic model.
19 pages, 4 figures, added proofs for full version
Cited by in corpus (5)
- A Complete Dichotomy Rises from the Capture of Vanishing Signatures
- The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems
- The Complexity of Planar Boolean #CSP with Complex Weights
- Bipartite 3-Regular Counting Problems with Mixed Signs
- From Holant To #CSP And Back: Dichotomy For Holant Problems