BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:CQIF Seminar
SUMMARY:Relaxations of Graph Isomorphism - David Roberson\
, UCL
DTSTART;TZID=Europe/London:20161013T141500
DTEND;TZID=Europe/London:20161013T151500
UID:TALK67570AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/67570
DESCRIPTION:We introduce a two player non-local game based on
graph isomorphisms. In the (X\,Y)-isomorphism game
the players aim to convince a referee that there
exists an isomorphism between graphs X and Y. Clas
sically\, players can win this game with probabili
ty one if and only if the graphs are isomorphic. T
his allows us to define a quantum analog of isomor
phism in the same manner as quantum coloring/homom
orphism was defined. This notion of "quantum isomo
rphism" can be expressed in terms of a feasibility
program over the recently introduced completely p
ositive semidefinite cone. We can thus give relaxa
tions of quantum isomorphism by considering the sa
me program\, but over the positive semidefinite or
doubly nonnegative cones. The doubly nonnegative
relaxation turns out to be equivalent to a previou
sly defined notion based on coherent algebras asso
ciated to graphs. Interestingly\, the main idea be
hind the proof of this equivalence is based on Cho
i matrices and CPTP unital maps. Another relaxatio
n can be obtained by considering general non-signa
lling strategies for the isomorphism game. This re
laxation turns out to be equivalent to a linear re
laxation of graph isomorphism known as fractional
isomorphism. Lastly\, we give a construction of pa
irs graphs based on linear binary constraint syste
ms and the FGLSS-reduction that are quantum isomor
phic but not isomorphic.\n\nJoint work with Albert
Atserias\, Laura Mancinska\, Robert Samal\, Simon
e Severini\, and Antonios Varvitsiotis.\n
LOCATION:MR4\, Centre for Mathematical Sciences\, Wilberfor
ce Road\, Cambridge
CONTACT:Steve Brierley
END:VEVENT
END:VCALENDAR