Holant Problems for Regular Graphs with Complex Edge Functions

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/inria-00455751
Contributor : Publications Loria <>
Submitted on : Thursday, February 11, 2010 - 10:09:31 AM
Last modification on : Wednesday, August 7, 2019 - 2:12:02 PM
Long-term archiving on : Friday, June 18, 2010 - 6:21:07 PM

File

Kowalczyk.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00455751, version 1

Collections

Citation

Michael Kowalczyk, Jin-Yi Cai. Holant Problems for Regular Graphs with Complex Edge Functions. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Inria Nancy Grand Est & Loria, Mar 2010, Nancy, France. pp.525-536. ⟨inria-00455751⟩

Share

Metrics

Record views

310

Files downloads

678