BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistingui
 shability - Peter Zeman (Technical University of Denmark)
DTSTART:20241203T111000Z
DTEND:20241203T115000Z
UID:TALK218608@talks.cam.ac.uk
DESCRIPTION:Mančinska and Roberson~[FOCS'20] showed that two graphs are q
 uantum isomorphic if and only if they are homomorphism indistinguishable o
 ver the class of planar graphs. Atserias et al.~[JCTB'19] proved that quan
 tum isomorphism is undecidable in general. The NPA hierarchy gives a seque
 nce of semidefinite programming relaxations of quantum isomorphism. Recent
 ly\, Roberson and Seppelt~[ICALP'23] obtained a homomorphism indistinguish
 ability characterization of the feasibility of each level of the Lasserre 
 hierarchy of semidefinite programming relaxations of graph isomorphism. We
  prove a quantum analogue of this result by showing that each level of the
  NPA hierarchy of SDP relaxations for quantum isomorphism of graphs is equ
 ivalent to homomorphism indistinguishability over an appropriate class of 
 planar graphs. By combining the convergence of the NPA hierarchy with the 
 fact that the union of these graph classes is the set of all planar graphs
 \, we are able to give a new proof of the result of Mančinska and Roberso
 n~[FOCS'20] that avoids the use of the theory of quantum groups. This homo
 morphism indistinguishability characterization also allows us to give a ra
 ndomized polynomial-time algorithm deciding exact feasibility of each fixe
 d level of the NPA hierarchy of SDP relaxations for quantum isomorphism.
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR