3 citations · 5 across the 5 of their papers we have counts for
4 papers · 1 filter
Spectral Methods for the Complexity of Planar Graph Homomorphisms
Ashwin Maran, Jin-Yi Cai, Zhuxiao Tang
We explore the frontier beyond the recently discovered barrier represented by the \emph{quantum automorphism group} in the classification theory of planar graph homomorphi…
Planar Graph Homomorphisms: A Dichotomy and a Barrier from Quantum Groups
Jin-Yi Cai, Ashwin Maran, Ben Young
We study the complexity of counting (weighted) planar graph homomorphism problem parametrized by an arbitrary symmetric non-negative real valued matrix .…
Polynomial and analytic methods for classifying complexity of planar graph homomorphisms
Jin-Yi Cai, Ashwin Maran
We introduce some polynomial and analytic methods in the classification program for the complexity of planar graph homomorphisms. These methods allow us to handle infinitely many l…
The complexity of counting planar graph homomorphisms of domain size 3
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 defining a graph homomorphism fr…