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

arXiv:1108.3383

Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy

Jin‐Yi Cai, Michael Kowalczyk, Tyson Williams

Published Aug 17, 2011• 0 citations
arXivHTMLPDF

Abstract

We introduce an idea called anti-gadgets in complexity reductions. These combinatorial gadgets have the effect of erasing the presence of some other graph fragment, as if we had managed to include a negative copy of a graph gadget. We use this idea to prove a complexity dichotomy theorem for the partition function $Z(G)$ on 3-regular directed graphs $G$, where each edge is given a complex-valued binary function $f: \{0,1\}^2 \rightarrow \mathbb{C}$. We show that \[Z(G) = \sum_{σ: V(G) \to \{0,1\}} \prod_{(u,v) \in E(G)} f(σ(u), σ(v)),\] is either computable in polynomial time or #P-hard, depending explicitly on $f$.

DOI
10.48550/arxiv.1108.3383

Related papers

Gadgets and anti-gadgets leading to a complexity dichotomy

Jin‐Yi Cai, Michael Kowalczyk, Tyson Williams

We introduce an idea called anti-gadgets in complexity reductions. These combinatorial gadgets have the effect of erasing the presence of some other graph fragment, as if we had managed to include a negative copy of a graph gadget. We use this idea to prove a complexity dichotomy theorem for the partition function Z(G) on 3-regular directed graphs G, where each edge is given a complex-valued binary function f: {0,1}2 → C. We show that

Conference on Innovations in Theoretical Computer Science•Jan 8, 2012•14 citations

Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy

Jin‐Yi Cai, Michael Kowalczyk, Tyson Williams

We introduce an idea called anti-gadgets for reductions in complexity theory. These anti-gadgets are presented as graph fragments, but their effect is equivalent to erasing the presence of other graph fragments, as if we had managed to include a negative copy of a certain graph gadget. We use this idea to prove a complexity dichotomy theorem for the partition function Z ( G ) of spin systems over 3-regular directed graphs G , Z ( G ) = ∑ σ : V ( G ) → { 0,1} ∏ ( u , v ) ∈ E ( G ) f (σ ( u ), σ ( v )), where each edge is given a (not necessarily symmetric) complex-valued binary function f : { 0,1} 2 → C. We show that Z ( G ) is either computable in polynomial time or #P-hard, depending explicitly on f . When the input graph G is planar, there is an additional class of polynomial time computable partition functions Z ( G ), while everything else remains #P-hard. Furthermore, this additional class is precisely those that can be transformed by a holographic reduction to matchgates, followed by the Fisher-Kasteleyn-Temperley algorithm via Pfaffians.

ACM Transactions on Computation Theory•Feb 17, 2019•6 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

Planar Graph Homomorphisms: A Dichotomy and a Barrier from Quantum Groups

Jin‐Yi Cai, Ashwin Maran, Ben Young

We study the complexity of counting (weighted) planar graph homomorphism problem $\tt{Pl\text{-}GH}(M)$ parametrized by an arbitrary symmetric non-negative real valued matrix $M$. For matrices with pairwise distinct diagonal values, we prove a complete dichotomy theorem: $\tt{Pl\text{-}GH}(M)$ is either polynomial-time tractable, or $\#$P-hard, according to a simple criterion. More generally, we obtain a dichotomy whenever every vertex pair of the graph represented by $M$ can be separated using some planar edge gadget. A key question in proving complexity dichotomies in the planar setting is the expressive power of planar edge gadgets. We build on the framework of Mančinska and Roberson to establish links between \textit{planar} edge gadgets and the theory of the \textit{quantum automorphism group} $\tt{Qut}(M)$. We show that planar edge gadgets that can separate vertex pairs of $M$ exist precisely when $\tt{Qut}(M)$ is \emph{trivial}, and prove that the problem of whether $\tt{Qut}(M)$ is trivial is undecidable. These results delineate the frontier for planar homomorphism counting problems and uncover intrinsic barriers to extending nonplanar reduction techniques to the planar setting.

arXiv:2601.23198•Jan 30, 2026•5 citations

A Complexity Trichotomy for the Six-Vertex Model.

Jin‐Yi Cai, Zhiguo Fu, Shuai Shao

We prove a complexity classification theorem that divides the six-vertex model on graphs into exactly three types. For every setting of the parameters of the model, the computation of the partition function is precisely: Either (1) solvable in polynomial time for every graph, or (2) #P-hard for general graphs but solvable in polynomial time for planar graphs, or (3) #P-hard even for planar graphs. The classification has an explicit criterion. In addition to matchgates and matchgates-transformable signatures, we discover previously unknown families of planar-tractable partition functions by a non-local connection to #CSP, defined in terms of a loop space. For the proof of #P-hardness, we introduce the use of M\obius transformations as a powerful new tool to prove that certain complexity reductions succeed in polynomial time.

•Apr 5, 2017•2 citations
We introduce an idea called anti-gadgets in complexity reductions. These combinatorial gadgets have the effect of erasing the presence of some other graph fragment, as if we had managed to include a negative copy of a graph gadget. We use this idea to prove a complexity dichotomy theorem for the partition function Z(G)Z(G)Z(G) on 3-regular directed graphs GGG, where each edge is given a complex-valued binary function f:{0,1}2→Cf: \{0,1\}^2 \rightarrow \mathbb{C}f:{0,1}2→C. We show that [Z(G) = \sum_{σ: V(G) \to {0,1}} \prod_{(u,v) \in E(G)} f(σ(u), σ(v)),] is either computable in polynomial time or #P-hard, depending explicitly on fff.
We introduce an idea called anti-gadgets for reductions in complexity theory. These anti-gadgets are presented as graph fragments, but their effect is equivalent to erasing the presence of other graph fragments, as if we had managed to include a negative copy of a certain graph gadget. We use this idea to prove a complexity dichotomy theorem for the partition function Z ( G ) of spin systems over 3-regular directed graphs G , Z ( G ) = ∑ σ : V ( G ) → { 0,1} ∏ ( u , v ) ∈ E ( G ) f (σ ( u ), σ ( v )), where each edge is given a (not necessarily symmetric) complex-valued binary function f : { 0,1} 2 → C. We show that Z ( G ) is either computable in polynomial time or #P-hard, depending explicitly on f . When the input graph G is planar, there is an additional class of polynomial time computable partition functions Z ( G ), while everything else remains #P-hard. Furthermore, this additional class is precisely those that can be transformed by a holographic reduction to matchgates, followed by the Fisher-Kasteleyn-Temperley algorithm via Pfaffians.
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.
We study the complexity of counting (weighted) planar graph homomorphism problem Pl-GH(M)\tt{Pl\text{-}GH}(M)Pl-GH(M) parametrized by an arbitrary symmetric non-negative real valued matrix MMM. For matrices with pairwise distinct diagonal values, we prove a complete dichotomy theorem: Pl-GH(M)\tt{Pl\text{-}GH}(M)Pl-GH(M) is either polynomial-time tractable, or #\##P-hard, according to a simple criterion. More generally, we obtain a dichotomy whenever every vertex pair of the graph represented by MMM can be separated using some planar edge gadget. A key question in proving complexity dichotomies in the planar setting is the expressive power of planar edge gadgets. We build on the framework of Mančinska and Roberson to establish links between \textit{planar} edge gadgets and the theory of the \textit{quantum automorphism group} Qut(M)\tt{Qut}(M)Qut(M). We show that planar edge gadgets that can separate vertex pairs of MMM exist precisely when Qut(M)\tt{Qut}(M)Qut(M) is \emph{trivial}, and prove that the problem of whether Qut(M)\tt{Qut}(M)Qut(M) is trivial is undecidable. These results delineate the frontier for planar homomorphism counting problems and uncover intrinsic barriers to extending nonplanar reduction techniques to the planar setting.
We prove a complexity classification theorem that divides the six-vertex model on graphs into exactly three types. For every setting of the parameters of the model, the computation of the partition function is precisely: Either (1) solvable in polynomial time for every graph, or (2) #P-hard for general graphs but solvable in polynomial time for planar graphs, or (3) #P-hard even for planar graphs. The classification has an explicit criterion. In addition to matchgates and matchgates-transformable signatures, we discover previously unknown families of planar-tractable partition functions by a non-local connection to #CSP, defined in terms of a loop space. For the proof of #P-hardness, we introduce the use of M\obius transformations as a powerful new tool to prove that certain complexity reductions succeed in polynomial time.