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
- Hanchen DaDaDash
- Interested Talks
- MR4, Centre for Mathematical Sciences, Wilberforce Road, Cambridge
- bld31
Note that ex-directory lists are not shown. |
## Other listsINI info aggregator Geometric Group Theory (GGT) Seminar Dio-Gandhi equations Tackling Obesity with Big Data: methods & models - One Day Seminar Mendeley Data - Viewer - 1975 PhD math international bio synthesis ... https://data.mendeley.com/.../2966f1cd-3b53-45bf-a685-1513718... Traduire cette page 7 nov. 2016 - ... Boudemagh, N (2016), “ENERGY EFFCIENCY”, Mendeley Data, v1 http://dx.doi.org/ Pharmacology Lunch Club## Other talksDevelopmental cognitive neuroscience What is the Market Potential of Multilingualism? A physical model for wheezing in lungs Prescribing step counts in type 2 diabetes and hypertension:Results of the Step Monitoring to improve ARTERial health trial Anglo-Ottoman encounter in the Age of the Beloveds |