Complexity Dichotomies for Counting Problems: Volume 1, Boolean Domain

Autor: Jin-Yi Cai, Xi Chen

Complexity theory aims to understand and classify computational problems, especially decision problems, according to their inherent complexity. This book uses new techniques to expand the theory for use with counting problems. The authors present dic

The complexity of counting planar graph homomorphisms of domain size 3

Autor: Jin-Yi Cai, Ashwin Maran

We prove a complexity dichotomy theorem for counting planar graph homomorphisms of domain size 3. Given any 3 by 3 real valued symmetric matrix $H$ defining a graph homomorphism from all planar graphs $G \mapsto Z_H(G)$, we completely classify the co

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::38665e53fdf7076bc3d5715463d26713
http://arxiv.org/abs/2302.08570

On a Theorem of Lovász that (&sdot, H ) Determines the Isomorphism Type of H

Autor: Artem Govorov, Jin-Yi Cai

Publikováno v: ACM Transactions on Computation Theory. 13:1-25

Graph homomorphism has been an important research topic since its introduction [20]. Stated in the language of binary relational structures in that paper [20], Lovász proved a fundamental theorem that, for a graph H given by its 0-1 valued adjacency

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::75b0b3d851f1b259efd5e3e593d3a57d
https://doi.org/10.1145/3448641

Where Tutte and Holant meet: a view from counting complexity

Autor: Jin-Yi Cai, Tyson Williams

Publikováno v: Handbook of the Tutte Polynomial and Related Topics ISBN: 9780429161612

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::2bc501551bf13d4f47e50a6f33ea28cb
https://doi.org/10.1201/9780429161612-21

FKT is not universal — A planar Holant dichotomy for symmetric constraints

Autor: Heng Guo, Zhiguo Fu, Jin-Yi Cai, Tyson Williams

Publikováno v: Cai, J-Y, Fu, Z, Guo, H & Williams, T 2022, ' FKT is not universal — A planar Holant dichotomy for symmetric constraints ', Theory of Computing Systems, vol. 66, pp. 143-308 . https://doi.org/10.1007/s00224-021-10032-1

We prove a complexity classification for Holant problems defined by an arbitrary set of complex-valued symmetric constraint functions on Boolean variables. This is to specifically answer the question: Is the Fisher-Kasteleyn-Temperley (FKT) algorithm

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::15a71eeaf76f8b5cc1592cb3ef8d46dc
https://hdl.handle.net/20.500.11820/d57c88d6-c3d7-4626-994e-08fa213e0a60