UCSB CS Theory Colloquium Series

Spring 2022

Friday, May 6, 2pm, Phelps 2510

Speaker: Alexandra Kolla (UC Santa Cruz)

Title: Statistical physics approaches to Unique Games

Abstract: We show how 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 and discuss promising current and future work. Based on joint work with M. Coulson, E. Davies, V. Patel, and G. Regts.