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.
Type de document :
Communication dans un congrès
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.525-536, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00455751
Contributeur : Publications Loria <>
Soumis le : jeudi 11 février 2010 - 10:09:31
Dernière modification le : jeudi 11 février 2010 - 11:18:26
Document(s) archivé(s) le : vendredi 18 juin 2010 - 18:21:07

Fichier

Kowalczyk.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00455751, version 1

Collections

Citation

Michael Kowalczyk, Jin-Yi Cai. Holant Problems for Regular Graphs with Complex Edge Functions. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.525-536, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00455751〉

Partager

Métriques

Consultations de la notice

261

Téléchargements de fichiers

274