2010/01/04 by Michael Kowalczyk, Kowalczyk, Michael, Jin‐Yi Cai +1 · 1 citation
Computer Science · Mathematics · #Computational Complexity (cs.CC) #F.2.1 #FOS: Computer and information sciences #Graph theory and applications #Markov Chains and Monte Carlo Methods #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1001.0464
openalex publication_date 2010/01/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.