Labeled graph framework for unique games

Zapraszamy w piątek 4.12.2020 o godz. 12:15 na seminarium.

Seminarium ONLINE pod tytułem: "Labeled graph framework for unique games" poprowadzi, Monika Rosicka UG

Abstract: We present a framework in which unique games are represented in the form of edge-labelings of graphs. We define an equivalence relation which preserves both classical and quantum values of games. We also show how the classical value of the game depends on the properties of the cycles within the labeled graph. In particular, we relate the problem of computing the classical value of single-party anti-correlation XOR games to finding the edge bipartization number of a graph, and connect the computation of the classical value of XOR-d games to the identification of specific cycles in the graph. In some specific cases this approach allows us to calculate the classical values of games