4 papers
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 .…
Vanishing Signatures, Orbit Closure, and the Converse of the Holant Theorem
Jin-Yi Cai, Ben Young
Valiant's Holant theorem is a powerful tool for algorithms and reductions for counting problems. It states that if two sets and of tensors (a.k.a. const…
Quantum Algorithms for Discrete Log Require Precise Rotations
Jin-Yi Cai, Ben Young
Recently, Cai showed that Shor's quantum factoring algorithm fails to factor large integers when the algorithm's quantum Fourier transform (QFT) is corrupted by a vanishing level o…
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…