Kurt Girstmair

dblp:126/6956 · DBLP profile ↗
← Back
3ranked-venue papers
1as first author
2since 2021 · last 2023
0000-0003-3105-5111ORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 3 · 1 first-author · 2 since 2021
YearPublicationVenuePosition
2023 A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory
Jin-Yi Cai, Zhiguo Fu, Kurt Girstmair, Michael Kowalczyk
Comput. Complex.3
2021 Reducing radicals in the spirit of Euclid
Kurt Girstmair
J. Symb. Comput.1
2018 A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory
abstract
Suppose \varphi and \psi are two angles satisfying \tan(\varphi) = 2 \tan(\psi) > 0. We prove that under this condition \varphi and \psi cannot be both rational multiples of \pi. We use this number theoretic result to prove a classification of the computational complexity of spin systems on k-regular graphs with general (not necessarily symmetric) real valued edge weights. We establish explicit criteria, according to which the partition functions of all such systems are classified into three classes: (1) Polynomial time computable, (2) \#P-hard in general but polynomial time computable on planar graphs, and (3) \#P-hard on planar graphs. In particular problems in (2) are precisely those that can be transformed to a form solvable by the Fisher-Kasteleyn-Temperley algorithm by a holographic reduction.
Jin-Yi Cai, Zhiguo Fu, Kurt Girstmair, Michael Kowalczyk
ITCS3