Result: Holant Problems for Regular Graphs with Complex Edge Functions
Title:
Holant Problems for Regular Graphs with Complex Edge Functions
Authors:
Contributors:
Department of Mathematics and Computer Science, Northern Michigan University, Department of Computer Sciences [Madison] (CS), University of Wisconsin-Madison, Inria Nancy Grand Est & Loria, Jean-Yves Marion and Thomas Schwentick
Source:
27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010. :525-536
Publisher Information:
HAL CCSD, 2010.
Publication Year:
2010
Collection:
collection:STACS2010
Subject Terms:
Subject Geographic:
Original Identifier:
HAL:
Document Type:
Conference
conferenceObject<br />Conference papers
Language:
English
Access URL:
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.inria.00455751v1
Database:
HAL
Further Information
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.