Abstract

 Mancinska and Roberson recently proved that two graphs are quantum isomorphic iff they define the same graph homomorphism partition function from all planar graphs.  We extend this result to all counting constraint satisfaction problems.

Separately, we prove a complexity dichotomy theorem for all real-valued planar graph homomorphism partition functions on domain size 3.

Based on joint work with Ben Young, and with Ashwin Maran.

Time

2023-07-07  10:00 - 11:00   

Speaker

Jin-Yi Cai, University of Wisconsin--Madison

Room

Room 308