COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

## Relaxations of Graph IsomorphismAdd to your list(s) Download to your calendar using vCal - David Roberson, UCL
- Thursday 13 October 2016, 14:15-15:15
- MR4, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.
If you have a question about this talk, please contact Steve Brierley. 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. Classically, players can win this game with probability one if and only if the graphs are 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 program over the recently introduced completely positive semidefinite cone. We can thus give relaxations of quantum isomorphism by considering the same program, but over the positive semidefinite or doubly nonnegative cones. The doubly nonnegative relaxation turns out to be equivalent to a previously defined notion based on coherent algebras associated to graphs. Interestingly, the main idea behind the proof of this equivalence is based on Choi matrices and CPTP unital maps. Another relaxation can be obtained by considering general non-signalling strategies for the isomorphism game. This relaxation turns out to be equivalent to a linear relaxation of graph isomorphism known as fractional isomorphism. Lastly, we give a construction of pairs graphs based on linear binary constraint systems and the FGLSS -reduction that are quantum isomorphic but not isomorphic. Joint work with Albert Atserias, Laura Mancinska, Robert Samal, Simone Severini, and Antonios Varvitsiotis. This talk is part of the CQIF Seminar series. ## This talk is included in these lists:- All CMS events
- CMS Events
- CQIF Seminar
- DAMTP info aggregator
- MR4, Centre for Mathematical Sciences, Wilberforce Road, Cambridge
Note that ex-directory lists are not shown. |
## Other listsMeeting the Challenge of Healthy Ageing in the 21st Century Synthetic Differential Geometry Seminar EED Film Series: 'City of God'## Other talks"Intestinal epithelial cells: at the interface of the microbiota and mucosal immunity" Adsorption-induced stresses and variations of permeability in coal seams during CO2 storage or CH4 production" Hypertension, Left Ventricular Remodelling and Heart Failure in Black Africans Using Data to Improve Decision Making in a Complex World Introduction to the biology of metastasis National crises, viewed in the light of personal crises w/ Prof Jared Diamond |