10.4230/LIPIcs.STACS.2010.2482
Kowalczyk, Michael
Cai, Jin-Yi
Holant Problems for Regular Graphs with Complex Edge Functions
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany
2010
Computer Science
000 Computer science, knowledge, general works
Herbstritt, Marc
2010-03-09
eng
ConferencePaper
12 pages
application/pdf
1.0
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC-BY-NC-ND)
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 \emph{in combination} succeed in proving \#P-hardness; and (3) algebraic symmetrization, which significantly lowers the \emph{symbolic complexity} of the proof for computational complexity. With \emph{holographic reductions} the classification theorem also applies to problems beyond the basic model.