Showing 2026Show all
3 papers · 1 filter
cs.CC2026
Group Action and Spin Representation Lead to a Holant* Complexity Dichotomy on Domain Size 3
Jin-Yi Cai, Jin Soo Ihm
We prove a complexity dichotomy theorem for problems over complex-valued symmetric constraint functions on domain size . We give a decidable tr…
cs.GT2026
Pure Nash Equilibria under the Affine Mechanism: A Potential Game of Exaggeration
Jason Jisen Li, Young Wu, Yancheng Zhu +2
The mean mechanism is known to be non-incentive-compatible, namely, rational players are incentivized to misreport their values. Despite this game-theoretic issue, the mean mechani…
cs.CC2026
New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model
Austen Fan, Jin-Yi Cai, Shuai Shao +1
We prove a complete complexity classification theorem for the planar eight-vertex model. For every parameter setting in for the eight-vertex model, the partition func…