17 November 2020

QMATH in FOCS 2020: Planar graphs and Quantum Mechanics


On Wednesday November 18 Laura Mančinska from QMATH will present her joint work with David E. Roberson (DTU Compute) at one of the top two theoretical computer science conferences, FOCS.

This work shows that entanglement-assisted strategies in a certain game based on graph isomorphism admit a purely combinatorial interpretation. Specifically, whether or not the quantum players can win the (G,H)-ismomrphism game with certainty is equivalent to graphs, G and H, having the same number of homomorphisms from any planar graph. Read more here https://arxiv.org/pdf/1910.06958.pdf
This year the conference is held virtually and you can see the recordings and the live talks here https://focs2020.cs.duke.edu/live-conference/ (registration required).