BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Relaxations of Graph Isomorphism - David Roberson\, UCL
DTSTART:20161013T131500Z
DTEND:20161013T141500Z
UID:TALK67570@talks.cam.ac.uk
CONTACT:Steve Brierley
DESCRIPTION:We introduce a two player non-local game based on graph isomor
 phisms. In the (X\,Y)-isomorphism game the players aim to convince a refer
 ee that there exists an isomorphism between graphs X and Y. Classically\, 
 players can win this game with probability one if and only if the graphs a
 re isomorphic. This allows us to define a quantum analog of isomorphism in
  the same manner as quantum coloring/homomorphism was defined. This notion
  of "quantum isomorphism" can be expressed in terms of a feasibility progr
 am over the recently introduced completely positive semidefinite cone. We 
 can thus give relaxations of quantum isomorphism by considering the same p
 rogram\, but over the positive semidefinite or doubly nonnegative cones. T
 he doubly nonnegative relaxation turns out to be equivalent to a previousl
 y defined notion based on coherent algebras associated to graphs. Interest
 ingly\, the main idea behind the proof of this equivalence is based on Cho
 i matrices and CPTP unital maps. Another relaxation can be obtained by con
 sidering general non-signalling strategies for the isomorphism game. This 
 relaxation turns out to be equivalent to a linear relaxation of graph isom
 orphism known as fractional isomorphism. Lastly\, we give a construction o
 f pairs graphs based on linear binary constraint systems and the FGLSS-red
 uction that are quantum isomorphic but not isomorphic.\n\nJoint work with 
 Albert Atserias\, Laura Mancinska\, Robert Samal\, Simone Severini\, and A
 ntonios Varvitsiotis.\n
LOCATION:MR4\, Centre for Mathematical Sciences\, Wilberforce Road\, Cambr
 idge
END:VEVENT
END:VCALENDAR