Cover Image

From an odd arity signature to a Holant dichotomy

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Meng, Boning, Wang, Juqiu, Xia, Mingji, Zheng, Jiayi
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The $\text{FP}^\text{NP}$ versus #P dichotomy for #EO
by: Meng, Boning, et al.
Published: (2025)

P-time Algorithms for Typical #EO Problems
by: Meng, Boning, et al.
Published: (2024)

The framework to unify all complexity dichotomy theorems for Boolean tensor networks
by: Xia, Mingji
Published: (2026)

A full dichotomy for Holant$^c$, inspired by quantum computation
by: Backens, Miriam
Published: (2022)

The Counting General Dominating Set Framework
by: Zheng, Jiayi, et al.
Published: (2026)

Matchgate signatures under variable permutations
by: Meng, Boning, et al.
Published: (2025)

Parameterised Holant Problems
by: Aivasiliotis, Panagiotis, et al.
Published: (2024)

Symmetric Parameterised Holants on Hypergraphs: Towards a Classification for Parameterised VCSPs
by: Aivasiliotis, Panagiotis, et al.
Published: (2025)

Holant* Dichotomy on Domain Size 3: A Geometric Perspective
by: Cai, Jin-Yi, et al.
Published: (2025)

A combinatorial view of Holant problems on higher domains
by: Liu, Yin
Published: (2024)

Dichotomies for \#CSP on graphs that forbid a clique as a minor
by: Meng, Boning, et al.
Published: (2025)

Towards infinite PCSP: a dichotomy for monochromatic cliques
by: Banakh, Demian, et al.
Published: (2026)

A topological proof of the Hell-Nešetřil dichotomy
by: Meyer, Sebastian, et al.
Published: (2024)

A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs
by: Ducoffe, Guillaume
Published: (2026)

Towards a complexity-theoretic dichotomy for TQFT invariants
by: Bridges, Nicolas, et al.
Published: (2025)

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
by: Kim, Eun Jung, et al.
Published: (2022)

An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments
by: Feller, Roman, et al.
Published: (2024)

Complex Boolean Turing Machines: An Algebraic Semantic Framework for Computational Complexity
by: Zheng, Bojin, et al.
Published: (2026)

Dual-Tape Perspective and Generator Independence: The Algebraic Foundation of Real Boolean Turing Machines
by: Zheng, Jingwen, et al.
Published: (2026)

The Radical Solution and Computational Complexity
by: Zheng, Bojin, et al.
Published: (2024)

From Alternation to FPRAS: Toward a Complexity Classification of Approximate Counting
by: Hecher, Markus, et al.
Published: (2025)

From FPT Decision to FPT Enumeration
by: Creignou, Nadia, et al.
Published: (2025)

From Proof Complexity to Circuit Complexity via Interactive Protocols
by: Arteche, Noel, et al.
Published: (2024)

Near Optimal Hardness of Approximating $k$-CSP
by: Minzer, Dor, et al.
Published: (2025)

Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding under ETH
by: Gupta, Rishav, et al.
Published: (2026)

New Direct Sum Tests
by: Westover, Alek, et al.
Published: (2024)

3-Query RLDCs are Strictly Stronger than 3-Query LDCs
by: Gur, Tom, et al.
Published: (2025)

Training Cross-Morphology Embodied AI Agents: From Practical Challenges to Theoretical Foundations
by: Liu, Shaoshan, et al.
Published: (2025)

Kernelization dichotomies for hitting minors under structural parameterizations
by: Bougeret, Marin, et al.
Published: (2025)

A dichotomy theorem for $Γ$-switchable $H$-colouring on $m$-edge coloured graphs
by: Brewster, Richard, et al.
Published: (2023)

A New Reduction Method from Multivariate Polynomials to Univariate Polynomials
by: Wang, Cancan, et al.
Published: (2024)

Decision algorithms for reversibility of one-dimensional non-linear cellular automata under null boundary conditions
by: Junchi, Ma, et al.
Published: (2024)

From Pseudorandomness to Multi-Group Fairness and Back
by: Dwork, Cynthia, et al.
Published: (2023)

PSMC: Provable and Scalable Algorithms for Motif Conductance Based Graph Clustering
by: Lin, Longlong, et al.
Published: (2024)

The Algebraic Cost of a Boolean Sum
by: Orzel, Ian, et al.
Published: (2025)

Strong Inapproximability for a Promise Rank Problem
by: Guruswami, Venkatesan, et al.
Published: (2026)

Beyond Bilinear Complexity: What Works and What Breaks with Many Modes?
by: Brand, Cornelius, et al.
Published: (2026)

How Pinball Wizards Simulate a Turing Machine
by: Adejoh, Rosemary, et al.
Published: (2025)

Closure under factorization from a result of Furstenberg
by: Bhattacharjee, Somnath, et al.
Published: (2025)

Canonization of a random circulant graph by counting walks
by: Verbitsky, Oleg, et al.
Published: (2023)