From Block Orthogonality to Decidability in Complex-Weighted Counting CSP

arXiv:2608.14845 · cs.CC · Submitted 2026-08-14 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "From Block Orthogonality to Decidability in Complex-Weighted Counting CSP".

Jane: Here's the gist of the paper. In this paper, authors provide a total exact decision procedure for checking whether the three tractability conditions characterizing the polynomial-time side of a complex-weighted counting CSP dichotomy theorem hold on an unbounded family of generated instances, resolving a long-standing recognition gap The Three Tractability Conditions The paper formalizes three conditions—Block Orthogonality (BO), Type Partition (TP), and preservation by a common Mal’tsev operation (Mal)—that characterize the polynomial-time side of the dichotomy theorem for complex-weighted counting CSPs The authors define these as BO(F), TP(F), and Mal(F) and show that their conjunction is equivalent to Block Orthogonality, i.e., CC(F) = BO(F) ∧ TP(F) ∧ Mal(F) is equivalent to BO(F) Decidability and Structural Collapse The main result establishes that the conjunction of these three conditions is equivalent to Block Orthogonality, meaning CC(F) ⇐⇒ BO(F) The authors prove this by showing that Block Orthogonality alone forces both Type Partition and the existence of a single Mal’tsev operation preserving all generated support and row-equivalence relations, collapsing the three-condition characterization to Block Orthogonality This structural collapse is achieved through constructions involving power amplification, generated support detectors, and common Mal’tsev operations Algorithmic Framework A total exact decision procedure (Procedure 6.1) is constructed that decides whether CC(F) holds on the full unbounded family WF by combining the external-arity bound of d squared + 1 with universal identity testing over all finite labelled instances This procedure runs in a finite number of steps because it relies on a finite set of Block Orthogonality certificates Qk and a total exact oracle for polynomial identities Theorem 5.7 Degree-Multiple Extension The framework is extended to the degree-multiple generated family WδF, where every variable has an occurrence degree divisible by δ, and a cyclic root-of-unity degree filter is used to reduce the problem to finitely many ordinary character comparisons on Mkδ This extension allows for uniform decidability of the three tractability conditions on WδF for every positive degree modulus δ The paper provides a total exact decision procedure that decides the three tractability conditions characterizing the polynomial-time side of the complex-weighted counting CSP dichotomy theorem, and moreover, Global Block Orthogonality forces the Type Partition and common Mal’tsev conditions from that dichotomy theorem The final result is that BO(F) is equivalent to CC(F) References

Bac21: Miriam Backens.

Tom: A full dichotomy for Holantc, inspired by quantum computation

Bac25: Miriam Backens.

Jane: Erratum: A full dichotomy for Holantc, inspired by quantum computation

BG05: Andrei A.

Tom: Bulatov and Martin Grohe.

Paper summary: Tom: So to wrap up this talk about "From Block Orthogonality to Decidability in Complex-Weighted Counting CSP," what’s the big picture implication for us as engineers?

Jane: It settles that long-standing recognition gap they mentioned, proving that we can always decide if those three tractability conditions are met on the full unbounded family WF >

Lu: And more importantly, it shows that Block Orthogonality is the central concept; it’s what you need to check to confirm Type Partition and the Mal’tsev condition simultaneously >

Meng: So for someone building a system based on these counting problems, it means they only have to worry about checking Block Orthogonality and not having to separately verify those other two conditions >

Tom: Right. The authors provide a total exact algorithm that decides these three conditions on the full unbounded family WF, which is what makes this result so powerful >

Jane: It’s a very constructive result, even if the procedure relies on things like external-arity compression and Skolem–Mahler–Lech theorem to ensure termination of those searches >

Lalam: The final result is that BO F is equivalent to CC F, which means Block Orthogonality is precisely what you need for this part of the dichotomy theorem >

Tom: It gives us a clear path forward for classifying the complexity side of these counting problems in the real world, by giving us a concrete decision procedure >

Jane: So they've taken an abstract classification and given us a verifiable test that works for any finite domain D and any finite algebraic complex language F >

Conclusion: Tom: So we're wrapping up this look at "From Block Orthogonality to Decidability in Complex-Weighted Counting CSP." Basically, the authors proved they found a total exact way to check if those three tractability conditions hold on all these complex counting problems.

Jane: Right, so the core of it is that they solved that long recognition gap we talked about earlier. It's about finding a definite test for whether those three things are true across every single instance they can generate.

Lu: What’s really interesting is how they showed that checking just one condition, Block Orthogonality, forces the other two conditions to be true automatically. It collapses the three-part check into just one central idea.

Meng: From a deployment standpoint, that means for someone actually running these algorithms, they don't need to worry about separately verifying Type Partition or that common Mal’tsev operation. Block Orthogonality is the main thing they have to track.

Tom: So it boils down to proving that Block Orthogonality is enough—it forces the whole structure into place for them. That's a strong structural result there, showing how interconnected those conditions really are.

Jane: It gives us a clear path forward for classifying the complexity side of these counting problems in the real world, by giving us a concrete test that works for any finite domain and any complex language they can build.

Lu: And they extend this idea to degree-multiple families, which is useful because it lets you handle problems where every variable has some specific structure on how many times it appears.

Meng: If you're looking at scaling up production systems, that uniform decidability across those different degree levels is something we need to think about for stability.

Tom: It gives us a solid foundation for knowing exactly when a problem falls into the polynomial time side of this complex counting dichotomy theorem. That’s a big win for anyone trying to build reliable solvers.

Jane: Now, with this decision procedure in hand, we can start looking at what happens when we move from the general family to more specific setups, like those degree-multiple families they mentioned earlier.

Chenghua Liu, Boning Meng

Institute of Software, Chinese Academy of Sciences · University of Regensburg

cs.CC

Submitted: 2026-08-14

Updated: 2026-11-06

Comments: 68 pages; revised proof and exposition, including a correction; Lean repository linked

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 93/100

The gist: In this paper, authors provide a total exact decision procedure for checking whether the three tractability conditions characterizing the polynomial-time side of a complex-weighted counting CSP…

Key concepts

Block Orthogonality (BO)
This is a key structural property of CSPs related to how constraints interact. The paper shows that if a problem satisfies Block Orthogonality, it forces the existence of Type Partition and a common Mal'tsev operation, simplifying the characterization significantly.
Type Partition (TP)
This condition relates to how the variables in a CSP can be grouped or partitioned based on their constraints. The authors demonstrate that Block Orthogonality implies this partitioning structure, which is crucial for understanding the problem's complexity.
Common Mal'tsev Operation (Mal)
A Mal'tsev operation is a specific algebraic structure used to analyze CSPs. The paper shows that Block Orthogonality forces the existence of a single Mal'tsev operation that preserves certain relations, collapsing the three tractability conditions into just Block Orthogonality.
Total Exact Decision Procedure
This is an algorithm designed to definitively answer whether a given complex-weighted CSP family satisfies its tractability conditions. The procedure runs in a finite number of steps because it relies on a finite set of certificates and an oracle for polynomial identities.

Terminology

Summary

In this paper, authors provide a total exact decision procedure for checking whether the three tractability conditions characterizing the polynomial-time side of a complex-weighted counting CSP dichotomy theorem hold on an unbounded family of generated instances, resolving a long-standing recognition gap

The Three Tractability Conditions

The paper formalizes three conditions—Block Orthogonality (BO), Type Partition (TP), and preservation by a common Mal’tsev operation (Mal)—that characterize the polynomial-time side of the dichotomy theorem for complex-weighted counting CSPs The authors define these as BO(F), TP(F), and Mal(F) and show that their conjunction is equivalent to Block Orthogonality, i.e., CC(F) = BO(F) ∧ TP(F) ∧ Mal(F) is equivalent to BO(F)

Decidability and Structural Collapse

The main result establishes that the conjunction of these three conditions is equivalent to Block Orthogonality, meaning CC(F) ⇐⇒ BO(F) The authors prove this by showing that Block Orthogonality alone forces both Type Partition and the existence of a single Mal’tsev operation preserving all generated support and row-equivalence relations, collapsing the three-condition characterization to Block Orthogonality This structural collapse is achieved through constructions involving power amplification, generated support detectors, and common Mal’tsev operations

Algorithmic Framework

A total exact decision procedure (Procedure 6.1) is constructed that decides whether CC(F) holds on the full unbounded family WF by combining the external-arity bound of d squared + 1 with universal identity testing over all finite labelled instances This procedure runs in a finite number of steps because it relies on a finite set of Block Orthogonality certificates Qk and a total exact oracle for polynomial identities Theorem 5. p. 07

Degree-Multiple Extension

The framework is extended to the degree-multiple generated family WδF, where every variable has an occurrence degree divisible by δ, and a cyclic root-of-unity degree filter is used to reduce the problem to finitely many ordinary character comparisons on Mkδ This extension allows for uniform decidability of the three tractability conditions on WδF for every positive degree modulus δ

Conclusion

The paper provides a total exact decision procedure that decides the three tractability conditions characterizing the polynomial-time side of the complex-weighted counting CSP dichotomy theorem, and moreover, Global Block Orthogonality forces the Type Partition and common Mal’tsev conditions from that dichotomy theorem The final result is that BO(F) is equivalent to CC(F)

References

[Bac21] Miriam Backens. A full dichotomy for Holantc, inspired by quantum computation

[Bac25] Miriam Backens. Erratum: A full dichotomy for Holantc, inspired by quantum computation

[BG05] Andrei A. Bulatov and Martin Grohe. p. 3 The complexity of partition functions

[BJK05] Andrei A. Bulatov, Peter Jeavons, and Andrei A. p. 3 Krokhin. Classifying the complexity of constraints using finite algebras

[Bul13] Andrei A. Bulatov. The complexity of the counting constraint satisfaction problem

[Bul17] Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs

[CC17] Jin-Yi Cai and Xi Chen. Complexity of counting CSP with complex weights

[CCL13] Jin-Yi Cai, Xi Chen, and Pinyan Lu. Graph homomorphisms with complex values: A dichotomy theorem

[CCL16] Jin-Yi Cai, Xi Chen, and Pinyan Lu. Nonnegative weighted CSP: An effective complexity dichotomy

[CGW14] Jin-Yi Cai, Heng Guo, and Tyson Williams. The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems

[CGW16] Jin-Yi Cai, Heng Guo, and Tyson Williams. A complete dichotomy rises from the capture of vanishing signatures

[CI25] Jin-Yi Cai and Jin Soo Ihm. Holant∗ dichotomy on domain size 3: A geometric perspective

[CLX09] Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Holant problems and counting CSP

[CLX13] Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Dichotomy for Holant problems with a function on domain size 3

[CLX14] Jin-Yi Cai, Pinyan Lu, and Mingji Xia. The complexity of complex weighted Boolean CSP

[CM23] Jin-Yi Cai and Ashwin Maran. The complexity of counting planar graph homomorphisms of domain size 3

[CM24] Jin-Yi Cai and Ashwin Maran. Polynomial and analytic methods for classifying complexity of planar graph homomorphisms

[CMY26] Jin-Yi Cai, Ashwin Maran, and Ben Young. Planar graph homomorphisms: A dichotomy and a barrier from quantum groups

[Coh93] Henri Cohen. A Course in Computational Algebraic Number Theory, volume 138 of Graduate Texts in Mathematics

[DG00] Martin Dyer and Catherine Greenhill. The complexity of counting graph homomorphisms

[DG04] Martin Dyer and Catherine S. Greenhill. Corrigendum: The complexity of counting graph homomorphisms

[DGJ09] Martin Dyer, Leslie Ann Goldberg, and Mark Jerrum. The complexity of weighted Boolean CSP

[DR13] Martin Dyer and David Richerby. An effective dichotomy for the counting constraint satisfaction problem

[FV98] Tomás Feder and Moshe Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory

[GGJT10] Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, and Marc Thurley. A complexity dichotomy for partition functions with mixed signs

[GSS26] Jincheng Guan, Shuai Shao, and Ke Shi. An LP algorithm for counting Eulerian orientations through the lens of quasi-polymorphism

[Lec53] Christer Lech. A note on recurring series

[LFC25] Yin Liu, Austen Z. Fan, and Jin-Yi Cai. p. 4 Restricted Holant dichotomy on domain sizes 3 and 4

[Lin21] Jiabao Lin. On the complexity of CSPd

[LW18] Jiabao Lin and Hanpin Wang. The complexity of Boolean Holant problems with nonnegative weights

[MWXZ25] Boning Meng, Juqiu Wang, Mingji Xia, and Jiayi Zheng. From an odd arity signature to a Holant dichotomy

[SC20] Shuai Shao and Jin-Yi Cai. A dichotomy for real Boolean Holant problems

[Sch78] Thomas J. Schaefer. The complexity of satisfiability problems

[Val08] Leslie G. Valiant. Holographic algorithms

[You25] Ben Young. Equality on all CSP instances yields constraint function isomorphism via interpolation and intertwiners

[Zhu17] Dmitriy Zhuk. A proof of CSP dichotomy conjecture

[Zhu20] Dmitriy Zhuk.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Global Block Orthogonality Decision Procedure allows for a total exact algorithm that decides whether Block Orthogonality holds on any generated family WF by combining an external-arity bound of d2 + 1 with universal identity testing over all finite labelled instances Mk.

  2. The system can decide the three tractability conditions (BO, TP, Mal) characterizing the polynomial-time side of the complex-weighted counting CSP dichotomy theorem for any degree multiple restriction Wdelta F.

  3. The system can determine which side of Lin's dichotomy theorem for degree-multiple counting CSP applies by checking BOdelta F, TPdelta F, and Maldelta F, as it is proven that BOdelta F implies both TPdelta F and Maldelta F.

  4. The system can solve the decision problem for arbitrary finite domain D and algebraic complex constraint language F by running Procedure 6.1, which halts on every input (D, F) and decides whether CC(F) holds on the full unbounded family WF.

  5. The system can verify that if BO(F) holds, there exists a single Mal'tsev operation m: D3 -> D such that for every G in WF, m preserves ΦG and every relation OmegaG for arity at least two.

Sources

Related papers