Dear all,

let me invite you to the next doctoral seminar (taking place tomorrow in S6 at 9:50). I will present the paper

"Computational Topology and the Unique Games Conjecture" by Joshua A. Grochow and Jamie Tucker-Foltz

which is accepted to SoCG 2018.

The Unique Games Conjecture states that, roughly speaking, a certain special type of CSP (Constraint Satisfaction Problem) called "Unique Games" is NP-hard to approximate within any constant factor. The conjecture has become known quite widely, because, if true, it implies that many approximation algorithms for NP-hard problems that we currently have are essentially optimal if P is not NP.

The authors of the aforementioned paper show that Unique Games is, in fact, a problem in computational topology of surfaces. Moreover, they present a new problem that is equivalent to the Unique Games Conjecture in terms of hardness of approximation.

The talk will be self-contained, no prior knowledge of Unique Games or Algebraic Topology is assumed. In particular, as a part of my talk, I will give a very accessible introduction to (a baby version of) homology and cohomology with examples.

Looking forward to seeing you in S6 tomorrow!

Best regards, Vojta