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

ACM Transactions on Computation Theory

Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy

Jin‐Yi Cai, Michael Kowalczyk, Tyson Williams

Published Feb 17, 2019• 6 citations
Publisher

Abstract

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.

DOI
10.1145/3305272

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 \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$.

arXiv:1108.3383•Aug 17, 2011•0 citations

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

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

Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP

Jin‐Yi Cai, Pinyan Lu, Mingji Xia

Valiant introduced matchgate computation and holographic algorithms. A number of seemingly exponential time problems can be solved by this novel algorithmic paradigm in polynomial time. We show that, in a very strong sense, matchgate computations and holographic algorithms based on them provide a universal methodology to a broad class of counting problems studied in the statistical physics community for decades. They capture precisely those problems which are #P-hard on general graphs but computable in polynomial time on planar graphs. More precisely, we prove complexity dichotomy theorems in the framework of counting CSP problems. The local constraint functions take Boolean inputs and can be arbitrary real-valued symmetric functions. We prove that every problem in this class belongs to precisely three categories: (1) those which are tractable (i.e., polynomial time computable) on general graphs, or (2) those which are #P-hard on general graphs but tractable on planar graphs, or (3) those which are #P-hard even on planar graphs. The classification criteria are explicit. Moreover, problems in category (2) are tractable on planar graphs precisely by holographic algorithms with matchgates.

arXiv:1008.0683•SIAM Journal on Computing•Jan 1, 2017•50 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
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 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)=∑σ:V(G)→{0,1}∏(u,v)∈E(G)f(σ(u),σ(v)),Z(G) = \sum_{σ: V(G) \to \{0,1\}} \prod_{(u,v) \in E(G)} f(σ(u), σ(v)),Z(G)=∑σ:V(G)→{0,1}​∏(u,v)∈E(G)​f(σ(u),σ(v)), is either computable in polynomial time or #P-hard, depending explicitly on fff.
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.
Valiant introduced matchgate computation and holographic algorithms. A number of seemingly exponential time problems can be solved by this novel algorithmic paradigm in polynomial time. We show that, in a very strong sense, matchgate computations and holographic algorithms based on them provide a universal methodology to a broad class of counting problems studied in the statistical physics community for decades. They capture precisely those problems which are #P-hard on general graphs but computable in polynomial time on planar graphs. More precisely, we prove complexity dichotomy theorems in the framework of counting CSP problems. The local constraint functions take Boolean inputs and can be arbitrary real-valued symmetric functions. We prove that every problem in this class belongs to precisely three categories: (1) those which are tractable (i.e., polynomial time computable) on general graphs, or (2) those which are #P-hard on general graphs but tractable on planar graphs, or (3) those which are #P-hard even on planar graphs. The classification criteria are explicit. Moreover, problems in category (2) are tractable on planar graphs precisely by holographic algorithms with matchgates.
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.