1 Search Results for "Coulson, Matthew"


Document
Statistical Physics Approaches to Unique Games

Authors: Matthew Coulson, Ewan Davies, Alexandra Kolla, Viresh Patel, and Guus Regts

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)


Abstract
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. The variant, which we call Count Unique Games, is a promise problem in which the "yes" case guarantees a certain number of highly satisfiable assignments to the Unique Games instance. In the standard Unique Games problem, the "yes" case only guarantees at least one such assignment. We exhibit efficient algorithms for Count Unique Games based on approximating a suitable partition function for the Unique Games instance 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 be strong negative evidence for the truth of the Unique Games Conjecture.

Cite as

Matthew Coulson, Ewan Davies, Alexandra Kolla, Viresh Patel, and Guus Regts. Statistical Physics Approaches to Unique Games. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 13:1-13:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{coulson_et_al:LIPIcs.CCC.2020.13,
  author =	{Coulson, Matthew and Davies, Ewan and Kolla, Alexandra and Patel, Viresh and Regts, Guus},
  title =	{{Statistical Physics Approaches to Unique Games}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{13:1--13:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.13},
  URN =		{urn:nbn:de:0030-drops-125650},
  doi =		{10.4230/LIPIcs.CCC.2020.13},
  annote =	{Keywords: Unique Games Conjecture, approximation algorithm, Potts model, cluster expansion, polynomial interpolation}
}
  • Refine by Author
  • 1 Coulson, Matthew
  • 1 Davies, Ewan
  • 1 Kolla, Alexandra
  • 1 Patel, Viresh
  • 1 Regts, Guus

  • Refine by Classification
  • 1 Mathematics of computing → Approximation algorithms
  • 1 Theory of computation → Algorithm design techniques
  • 1 Theory of computation → Approximation algorithms analysis

  • Refine by Keyword
  • 1 Potts model
  • 1 Unique Games Conjecture
  • 1 approximation algorithm
  • 1 cluster expansion
  • 1 polynomial interpolation

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail