From an odd arity signature to a Holant dichotomy

Boning Meng; Jiayi Zheng; Juqiu Wang; Mingji Xia

REVIEW 4 major objections 4 minor 12 references

From an odd arity signature to a Holant dichotomy

T0 review · 4 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A complete dichotomy now governs every Holant problem that contains a non-trivial odd-arity signature.

desk verdict A real advance in the Holant dichotomy program, conditional on the same group's unpublished #EO dichotomy; referee it, but check the black box and the asserted case analyses. read the letter →

arxiv 2502.05597 v1 pith:3SH63CFZ submitted 2025-02-08 cs.CC

Boning Meng , Juqiu Wang , Mingji Xia , Jiayi Zheng This is my paper · ORCID

classification cs.CC MSC 68Q1568Q17

keywords Holantcountingcomplexitydichotomy#P-hardFPNPoddaritysignaturesdecompositionlemma#EO

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves a complexity dichotomy for Holant problems over the Boolean domain when the signature set contains a non-trivial signature of odd arity. Such a problem is either #P-hard or in FPNP, with explicit conditions for each side. The authors also prove a generalized decomposition lemma that lets tensor products of signatures replace pairs of signatures unless the resulting problem's complexity is already known. Together these results close the last open column in the Holant classification table, restricting future work to even-arity signatures.

What carries the argument

The load-bearing mechanism is the generalized decomposition lemma (Theorem 32), which upgrades the earlier nonnegative-valued decomposition lemma to complex-valued signatures by invoking the #EO dichotomy in the exceptional case. Around it the proof assembles several established tools: the K holographic transformation into K-Holant, SLOCC classification of ternary signatures into GHZ and W types, unique prime factorization of signatures, and reductions from GHZ-type symmetric signatures to #CSP and #CSP2. The #EO dichotomy supplies the FPNP upper bound that appears in the final classification.

What would settle it

Exhibit a finite signature set F containing a non-trivial odd-arity signature for which Holant(F) is neither #P-hard nor in FPNP; the dichotomy says none exists. A more local falsifier targets Theorem 32: find signatures f,g and a set F such that Holant(F,f,g) and Holant(F,f⊗g) are not Turing-equivalent while Holant(F,f⊗g) is not decided by the #EO dichotomy.

Watch

Extended reading notes

Core claim

The central claim, stated as Theorem 33, is that for any finite set F of complex-valued Boolean signatures containing a non-trivial odd-arity signature, Holant(F) is #P-hard unless F falls into one of seven exceptional families, in which case the problem lies in FPNP or in polynomial time. The exceptions are described holographically: after the K transformation, the support of all signatures lies in HW≥ or HW≤ with the #EO conditions, or all signatures are single-weighted satisfying #EO conditions, or the original signature set is contained in ⟨T⟩, in ⟨M⟩, or is transformable into the affine, product, or local-affine classes A, P, or L. The companion Theorem 32 extends the decomposition lemma: for any signatures f,g and set F, Holant(F,f,g) is Turing-equivalent to Holant(F,f⊗g) unless the transformed set contains only HW≥ (or HW≤) signatures, in which case the complexity of Holant(F,f⊗g) is already classified by the #EO dichotomy.

Load-bearing premise

The entire classification leans on the #EO dichotomy proved in the same authors' recent papers, which is used as a black box; if that dichotomy has a gap, the exceptional cases and the FPNP side of the new result would not be established.

Editorial extensions

If this is right

Any Holant problem with a non-trivial odd-arity signature is now fully classified: it is either #P-hard, in FPNP, or in polynomial time, depending only on the finite signature set.
The generalized decomposition lemma provides a new reduction tool: pairs of signatures can be collapsed into their tensor product unless the #EO dichotomy already decides the resulting problem.
The result subsumes the previous real-valued Holantodd dichotomy and the Holantc dichotomy, giving a unified FPNP vs #P statement.
If a future work proves an FP vs #P dichotomy for #EO, Theorem 33 automatically sharpens to an FP vs #P dichotomy.
The only unclassified complex-valued Holant problems remain those in which every signature has even arity and is irreducible.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The paper's proof strategy suggests that any counterexample to the full Holant dichotomy, if one exists, must be built entirely from even-arity irreducible signatures with no odd-arity factor.
The reliance on the #EO dichotomy marks the FPNP upper bound as provisional; the dichotomy's boundary could migrate if the #EO classification is later sharpened.
The decomposition lemma's tensor-product collapse may be usable outside Holant, as a way to simplify holographic algorithm constructions by reducing the number of distinct constraint functions.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The short version: this is a real advance, and the main risk is exactly the one the stress-test names. Theorem 33 settles Holantodd for complex-valued signatures, leaving only the even-arity irreducible case, and Theorem 32 genuinely generalizes the decomposition lemma. Both are new, and both inherit fragility from the same source.

What the paper does well: the proof strategy is coherent and carefully mapped (Figures 1 and 2). It combines holographic transformations, SLOCC classification of ternary signatures, polynomial interpolation, and unique prime factorization in a way that extends the real-valued and Holantc techniques to the odd-arity complex setting. The paper is also honest about the FPNP vs #P limitation and about the fact that the #EO dichotomy is used as a black box. That transparency is credit-worthy.

The soft spots, in proportion. The load-bearing dependency is the same group's unpublished #EO dichotomy ([24], arXiv:2502.02012). Theorem 32's exceptional case invokes Corollary 30, and the tractable side of Theorem 33 is exactly the condition of that corollary; if [24] has a gap, the boundary of Theorem 33 shifts. This is not circular reasoning—the #EO dichotomy is a different class—but it is a correctness risk. The authors themselves say the proof is unfeasible without it, which is honest but confirms that the whole paper is conditional on that result.

Second, a few case analyses are asserted rather than shown. Lemma 58 in particular has 'it can always be verified' and then a long case list. The cases look plausible, and the detailed presentation given for Lemma 59 suggests the authors did work through them, but a referee would want these expanded or at least accompanied by a formal verification. Lemma 67 and Corollary 68 are brief but believable.

Net: conditional on [24], the main theorem holds up. The decomposition lemma is useful in itself, even if the odd-arity dichotomy needed a patch. I'd score soundness around 6, significance 8. This is a serious paper, not a desk reject. It should go to peer review with a referee asked to check the dependency on [24] and to expand the 'directly verified' steps.

Referee Report

4 major / 4 minor

Summary. The paper proves two main results for complex-valued Holant on the Boolean domain. Theorem 32 is a generalized decomposition lemma: it asserts that Holant(F,f,g) and Holant(F,f⊗g) are Turing-equivalent unless the transformed signature set F̂∪{f̂⊗ĝ} consists only of HW≥ or HW≤ signatures, in which case the complexity of Holant(F,f⊗g) is determined by the #EO dichotomy. Theorem 33 is a dichotomy for Holantodd: if F contains a non-trivial signature of odd arity, then Holant(F) is #P-hard unless one of seven conditions (PC) holds, with cases 1–2 in FPNP and cases 3–7 polynomial-time computable. The proof combines holographic transformations, SLOCC classifications, unique prime factorization, polynomial interpolation, and several existing dichotomies, and it explicitly relies on the #EO dichotomy of the same authors' preprints [23,24].

Significance. If the underlying #EO dichotomy is correct, the paper settles the complexity of every Holant problem with a non-trivial odd-arity signature, leaving only the even-arity irreducible case open. This is a substantial step: it subsumes the real-valued Holantodd dichotomy and parts of the Holantc dichotomy, and it extends the decomposition lemma to a complex-valued setting. The paper is honest about its main dependency: Section 3 states that the proof of Theorem 2 is infeasible without the #EO dichotomy. The reduction maps in Figures 1 and 2 are useful organizing devices, and the use of established machinery (UPF, SLOCC, interpolation) is appropriate. However, the central theorem is conditional on an unpublished, not-yet-peer-reviewed companion paper, and several load-bearing case analyses are presented as 'it can always be verified' or 'directly verified' rather than fully demonstrated.

major comments (4)

[Section 3, Theorems 32 and 33] The main theorems are not self-contained: Theorem 32's exceptional branch invokes Corollary 30, and Theorem 33's cases 1–2 and the corresponding hardness arguments invoke Theorem 29, Corollary 30, and Theorem 31, all of which are from the same authors' preprints [23,24] and are not proved in this manuscript. The text itself says in Section 3 that the proof of Theorem 2 is unfeasible in the absence of the #EO dichotomy. This is an external dependency rather than an internal contradiction, but it is load-bearing: if the #EO dichotomy has a gap, the FPNP tractable cases and the boundary between tractable and #P-hard in Theorem 33 lose support. Please either include complete proofs of the #EO dichotomy results used here or state the main theorems as explicitly conditional on a stable published version of [24].
[Lemma 67] The proof of the claim that every O∈O satisfies OK=KD or OK=KXD with D diagonal is not correct as written. In the case b=0, the matrices O=diag(-1,1) and O=diag(-1,-1) are omitted, even though they satisfy O∈O. In the cases a=0 and d=0, the displayed matrices include [[0,-2i],[2i,0]] and [[2i,0],[c,-2i]], which are not diagonal, and the latter contains an undefined c. Thus the stated decomposition is not established by the given argument. Since Corollary 68 and the reductions in the proof of Theorem 33 depend on Lemma 67, this is a load-bearing gap; the claim may be true, but the proof needs to be redone carefully.
[Lemma 58] The proof of Lemma 58 begins with the assertion that 'it can always be verified that at least one of these signatures does not belong to ⟨{Δ0,[1,1],[0,1,0]}⟩', but this verification is not carried out, and the subsequent case analysis repeatedly concludes 'we are done unless ...' without deriving the exceptional values from the irreducibility hypothesis. For example, in Case 2.1.2 the tensor-factorization contradiction is asserted rather than shown, and in Case 2.1.3 the deduction that s=0 is left implicit. Since Lemma 58 is used to handle irreducible ternary signatures in the W-type case of Lemma 35 and Theorem 33, this case analysis must be made complete.
[Lemma 59] The proof of the central 'statement' inside Lemma 59 contains several unproved claims: the inheritance property is used to assert inclusions of supports without derivation; in Case 2d the matrix g is declared not to belong to ⟨NR⟩ without proof; and in Case 3 the text says 'the analysis ... can be similarly applied' and 'it can be directly verified' at key points. Lemma 59 is the last step before applying Theorem 25 to close the exceptional case, so these gaps are load-bearing. Please provide a complete verification of every subcase, or replace the human case analysis with a machine-checked enumeration.

minor comments (4)

[Definition 28 and Theorems 29, 33] The two classes that are presumably ∀3↑ and ∀3↓ are both rendered as '∀3' in the text, making statements such as 'all signatures are ∀3 signatures or all signatures are ∀3 signatures' ambiguous; please use distinguishable symbols or names.
[Proof of Theorem 33, Case 4] The notation #CSPd is introduced without defining d; it should be #CSP_{2k+1} (or k) consistently with Lemma 61 and Lemma 43(4).
[Definitions 6 and 7] The displayed formula for Z(I) in Definition 6 is interrupted by Definition 7, and Definition 7's displayed equation appears before the sentence that defines Z(I); please reorder the text so each definition is self-contained.
[Introduction] The phrase 'the proof of Theorem 2 is unfeasible' should be 'infeasible', and the same typo appears in Section 3.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the Holantodd dichotomy is a new reduction result built on the separate #EO dichotomy; the #EO dependency is a verification risk, not a circular step.

full rationale

The claimed derivation is not circular. Theorem 33 is proved by reducing Holantodd to a small set of target problems: Holant(F, Delta0), K-Holant on HW>=/HW<= signature sets, K-Holantc on single-weighted signatures, and the #CSP/#CSP2/Holantc dichotomies. Each of these targets is a different problem class from the theorem being proved. The #EO dichotomy (Theorem 29, Corollary 30, Theorem 31 from [23,24]) is imported as a black box and is by the same group, and the paper explicitly says 'the proof of Theorem 2 is unfeasible in the absence of the dichotomy for #EO' and that FPNP is 'introduced due to the dichotomy for #EO in [24]'. That is a dependency, not circularity: the #EO dichotomy does not assume or contain the Holantodd dichotomy, and the present paper's hardness direction is carried by direct gadget reductions (Lemmas 43, 44, 50-59, 61-66) rather than by restating the #EO conditions. The exceptional conditions (PC) in Theorem 33 are not defined as 'tractable Holantodd' by construction; they are shown tractable via holographic transformations and the cited dichotomies, and every non-(PC) case is reduced to a known #P-hard problem. No equation in the paper defines a target quantity in terms of itself, and no fitted parameter is renamed as a prediction. The main risk—that [24] is an unpublished preprint from the same group—is a correctness and verification risk, not circularity.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The paper introduces no invented physical entities. Its free parameters are only existentially chosen matrices in holographic transformations (e.g., q, r, N), which are not fitted to data and do not encode the result; they are proof devices. The load-bearing content is a chain of reductions to established external dichotomies, the most fragile of which is the same group's #EO dichotomy (Theorem 29).

assumptions (7)

domain assumption Theorem 29 ([23,24]): #EO dichotomy: every set of EO signatures is either #P-hard or in FPNP, with explicit tractable structural conditions.
Used as a black box in Theorem 32 (via Corollary 30) and in the tractable side of Theorem 33. Not proved in this paper.
domain assumption Theorem 31 ([24]): K-Holant dichotomy for single-weighted signatures is #P-hard or in FPNP.
Used in the analysis of Case 2 and 3 of Lemma 43 (Section 5.2) and in the proof of Theorem 33.
domain assumption Theorem 20 ([16]): #CSP dichotomy for complex-valued Boolean signatures.
Used in Lemma 50 to convert Holant with a GHZ symmetric signature to #CSP, and in the proof of Lemma 35.
domain assumption Theorem 21 ([17]): #CSP2 dichotomy.
Used in the proof of Lemma 35 (second situation of Lemma 44) via Lemma 46 and in the proof of Theorem 33.
domain assumption Theorem 25 ([3]): Holantc dichotomy.
Used to classify complexity when Delta1 can be realized (Lemma 44, Case 3) and in the k=2 case of Theorem 33.
standard math Lemma 14 ([19]): SLOCC classification of ternary irreducible signatures into GHZ type and W type.
Used in Section 5.1 to classify irreducible ternary signatures (Step 3 of the proof strategy).
standard math Lemma 13 ([8]): if all self-loops of a signature vanish then its support avoids intermediate Hamming weights.
Used in Lemma 43 to show the support has only extreme weights when all self-loop reductions vanish.

how reviews work

0 comments

Cite this review

Pith. "Pith review of From an odd arity signature to a Holant dichotomy." pith.science (2026). https://pith.science/paper/3SH63CFZ

@misc{pith2026250205597,
  author       = {Pith},
  title        = {Pith review of: From an odd arity signature to a Holant dichotomy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3SH63CFZ}},
  note         = {Machine review of arXiv:2502.05597}
}

abstract

\textsf{Holant} is an essential framework in the field of counting complexity. For over fifteen years, researchers have been clarifying the complexity classification for complex-valued \textsf{Holant} on the Boolean domain, a challenge that remains unresolved. In this article, we prove a complexity dichotomy for complex-valued \textsf{Holant} on Boolean domain when a non-trivial signature of odd arity exists. This dichotomy is based on the dichotomy for \textsf{\#EO}, and consequently is an $\text{FP}^\text{NP}$ vs. \#P dichotomy as well, stating that each problem is either in $\text{FP}^\text{NP}$ or \#P-hard. Furthermore, we establish a generalized version of the decomposition lemma for complex-valued \textsf{Holant} on Boolean domain. It asserts that each signature can be derived from its tensor product with other signatures, or conversely, the problem itself is in $\text{FP}^\text{NP}$. We believe that this result is a powerful method for building reductions in complex-valued \textsf{Holant}, as it is also employed as a pivotal technique in the proof of the aforementioned dichotomy in this article.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 10 canonical work pages

[5]

15 Jin-Yi Cai, Pinyan Lu, and Mingji Xia

URL: https://doi.org/10.1145/ 1536414.1536511. 15 Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Dichotomy for Holant* problems of Boolean domain. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 1714–1728. SIAM,

work page arXiv
[8]

P-time Algorithms for Typical #EO Problems

URL: https://doi.org/10. 1137/17M113304X. 23 Boning Meng, Juqiu Wang, and Mingji Xia. P-time algorithms for typical #EO problems. arXiv preprint arXiv:2410.11557,

work page Pith review arXiv
[10]

Eulerian orientations and Hadamard codes: A novel connection via counting

26 Shuai Shao and Zhuxiao Tang. Eulerian orientations and Hadamard codes: A novel connection via counting. arXiv preprint arXiv:2411.02612,

work page Pith review arXiv
[2006]

28 Leslie G Valiant

URL: https://doi.org/10.1109/FOCS.2006.7. 28 Leslie G Valiant. Holographic algorithms.SIAM Journal on Computing, 37(5):1565–1594,

work page doi:10.1109/focs.2006.7 2006
[2008]

The computational complexity of Holant problems on 3-regular graphs.Theoretical Computer Science, 982:114256, 2024

29 Peng Yang, Yuan Huang, and Zhiguo Fu. The computational complexity of Holant problems on 3-regular graphs.Theoretical Computer Science, 982:114256, 2024

work page 2024
[2009]

A new Holant dichotomy inspired by quantum computation

2 Miriam Backens. A new Holant dichotomy inspired by quantum computation.arXiv preprint arXiv:1702.00767,

work page Pith review arXiv
[2011]

30 From an odd arity signature to a Holant dichotomy 16 Jin-Yi Cai, Pinyan Lu, and Mingji Xia

URL:https://doi.org/10.1137/1.9781611973082.132. 30 From an odd arity signature to a Holant dichotomy 16 Jin-Yi Cai, Pinyan Lu, and Mingji Xia. The complexity of complex weighted Boolean #CSP. Journal of Computer and System Sciences, 80(1):217–236,

doi:10.1137/1.9781611973082.132
[2013]

12 Jin-Yi Cai, Heng Guo, and Tyson Williams

URL: https: //doi.org/10.1145/2488608.2488687. 12 Jin-Yi Cai, Heng Guo, and Tyson Williams. A complete dichotomy rises from the capture of vanishing signatures. InProceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 635–644,

work page arXiv

Show all 12 references

[2016]

22 Jiabao Lin and Hanpin Wang

URL:https://doi.org/10.1007/s00037-015-0118-3. 22 Jiabao Lin and Hanpin Wang. The complexity of Boolean Holant problems with nonnegative weights. SIAM Journal on Computing, 47(3):798–828,

doi
[2018]

2018.01.003

URL: https://doi.org/10.1016/j.ic. 2018.01.003. 11 Jin-Yi Cai, Heng Guo, and Tyson Williams. A complete dichotomy rises from the capture of vanishing signatures. InProceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 635–644. Association for Comput...

2018 doi
[2020]

From Holant to quantum entanglement and back

9 Jin-Yi Cai, Zhiguo Fu, and Shuai Shao. From Holant to quantum entanglement and back. arXiv preprint arXiv:2004.05706,

2004 arXiv
[2025]

25 Shuai Shao and Jin-Yi Cai

URL: https://arxiv.org/abs/2502.02012, arXiv:2502.02012. 25 Shuai Shao and Jin-Yi Cai. A dichotomy for real Boolean Holant problems. In2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1091–1102. IEEE,

arXiv

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.

[1] [5]

15 Jin-Yi Cai, Pinyan Lu, and Mingji Xia

URL: https://doi.org/10.1145/ 1536414.1536511. 15 Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Dichotomy for Holant* problems of Boolean domain. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 1714–1728. SIAM,

work page arXiv

[2] [8]

P-time Algorithms for Typical #EO Problems

URL: https://doi.org/10. 1137/17M113304X. 23 Boning Meng, Juqiu Wang, and Mingji Xia. P-time algorithms for typical #EO problems. arXiv preprint arXiv:2410.11557,

work page Pith review arXiv

[3] [10]

Eulerian orientations and Hadamard codes: A novel connection via counting

26 Shuai Shao and Zhuxiao Tang. Eulerian orientations and Hadamard codes: A novel connection via counting. arXiv preprint arXiv:2411.02612,

work page Pith review arXiv

[4] [2006]

28 Leslie G Valiant

URL: https://doi.org/10.1109/FOCS.2006.7. 28 Leslie G Valiant. Holographic algorithms.SIAM Journal on Computing, 37(5):1565–1594,

work page doi:10.1109/focs.2006.7 2006

[5] [2008]

The computational complexity of Holant problems on 3-regular graphs.Theoretical Computer Science, 982:114256, 2024

29 Peng Yang, Yuan Huang, and Zhiguo Fu. The computational complexity of Holant problems on 3-regular graphs.Theoretical Computer Science, 982:114256, 2024

work page 2024

[6] [2009]

A new Holant dichotomy inspired by quantum computation

2 Miriam Backens. A new Holant dichotomy inspired by quantum computation.arXiv preprint arXiv:1702.00767,

work page Pith review arXiv

[7] [2011]

30 From an odd arity signature to a Holant dichotomy 16 Jin-Yi Cai, Pinyan Lu, and Mingji Xia

URL:https://doi.org/10.1137/1.9781611973082.132. 30 From an odd arity signature to a Holant dichotomy 16 Jin-Yi Cai, Pinyan Lu, and Mingji Xia. The complexity of complex weighted Boolean #CSP. Journal of Computer and System Sciences, 80(1):217–236,

doi:10.1137/1.9781611973082.132

[8] [2013]

12 Jin-Yi Cai, Heng Guo, and Tyson Williams

URL: https: //doi.org/10.1145/2488608.2488687. 12 Jin-Yi Cai, Heng Guo, and Tyson Williams. A complete dichotomy rises from the capture of vanishing signatures. InProceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 635–644,

work page arXiv