Document Open Access Logo

Holant Problems for Regular Graphs with Complex Edge Functions

Authors Michael Kowalczyk, Jin-Yi Cai



PDF
Thumbnail PDF

File

LIPIcs.STACS.2010.2482.pdf
  • Filesize: 330 kB
  • 12 pages

Document Identifiers

Author Details

Michael Kowalczyk
Jin-Yi Cai

Cite AsGet BibTex

Michael Kowalczyk and Jin-Yi Cai. Holant Problems for Regular Graphs with Complex Edge Functions. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 525-536, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
https://doi.org/10.4230/LIPIcs.STACS.2010.2482

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 \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.
Keywords
  • Computational complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail