Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

We show how two techniques from statistical physics can be adapted to solve a variant of the notorious Unique Games problem, potentially opening new avenues towards the Unique Games Conjecture.  We exhibit efficient algorithms for a natural generalisation of Unique Games based on approximating a suitable partition function via (i) a zero-free region and polynomial interpolation, and (ii) the cluster expansion.  We also show that a modest improvement to the parameters for which we give results would refute the Unique Games Conjecture. We also touch upon how techniques traditionally used to solve certain combinatorial optimization problems including special cases of Unique Games, can be used to make progress on statistical physics inspired questions, such as counting independent sets of bipartite graphs (#BIS).

Based on joint works with M. Coulson, E. Davies, V. Patel, and G. Regts,  Charlie Carlson,  Aditya Potuchi.