Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Theory of Computing Systems

Holant Problems for 3-Regular Graphs with Complex Edge Functions

Michael Kowalczyk, Jin‐Yi Cai

Published Mar 22, 2016• 20 citations
Publisher
DOI
10.1007/s00224-016-9671-7

Related papers

The computational complexity of Holant problems on 3-regular graphs

Peng Yang, Yuan Huang, Zhiguo Fu

Theoretical Computer Science•Oct 17, 2023•1 citation

Dichotomy for Non-negative Valued Holant Problems on 3-Regular Bipartite Graphs

Junda Li, Yuan Huang, Yanlin Zheng

Theory of Computing Systems•Jan 15, 2025•0 citations

A Dichotomy for k-Regular Graphs with {0, 1}-Vertex Assignments and Real Edge Functions

Jin‐Yi Cai, Michael Kowalczyk

Lecture notes in computer science•Jan 1, 2010•13 citations

State transfer in strongly regular graphs with an edge perturbation

Chris D. Godsil, Krystal Guo, Mark Kempton +2 more

arXiv:1710.02181•Journal of Combinatorial Theory Series A•Dec 12, 2019•15 citations

Holant Problems for Regular Graphs with Complex Edge Functions

Michael Kowalczyk, Jin‐Yi Cai

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.

arXiv:1001.0464•Jan 4, 2010•15 citations

Holant Problems for Regular Graphs with Complex Edge Functions

Michael Kowalczyk, Jin‐Yi Cai

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.

Leibniz international proceedings in informatics•Jan 1, 2010•15 citations
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.
We prove a complexity dichotomy theorem for Holant Problems on 333-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.