2 Search Results for "Regts, Guus"

Document
DOI: 10.4230/LIPIcs.CCC.2020.13
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}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.17
On a Theorem of Lovász that hom(⋅, H) Determines the Isomorphism Type of H

Authors: Jin-Yi Cai and Artem Govorov

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
Graph homomorphism has been an important research topic since its introduction [László Lovász, 1967]. Stated in the language of binary relational structures in that paper [László Lovász, 1967], Lovász proved a fundamental theorem that the graph homomorphism function G ↦ hom(G, H) for 0-1 valued H (as the adjacency matrix of a graph) determines the isomorphism type of H. In the past 50 years various extensions have been proved by Lovász and others [László Lovász, 2006; Michael Freedman et al., 2007; Christian Borgs et al., 2008; Alexander Schrijver, 2009; László Lovász and Balázs Szegedy, 2009]. These extend the basic 0-1 case to admit vertex and edge weights; but always with some restrictions such as all vertex weights must be positive. In this paper we prove a general form of this theorem where H can have arbitrary vertex and edge weights. An innovative aspect is that we prove this by a surprisingly simple and unified argument. This bypasses various technical obstacles and unifies and extends all previous known versions of this theorem on graphs. The constructive proof of our theorem can be used to make various complexity dichotomy theorems for graph homomorphism effective, i.e., it provides an algorithm that for any H either outputs a P-time algorithm solving hom(⋅, H) or a P-time reduction from a canonical #P-hard problem to hom(⋅, H).
Cite as

Jin-Yi Cai and Artem Govorov. On a Theorem of Lovász that hom(⋅, H) Determines the Isomorphism Type of H. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cai_et_al:LIPIcs.ITCS.2020.17,
  author =	{Cai, Jin-Yi and Govorov, Artem},
  title =	{{On a Theorem of Lov\'{a}sz that hom(⋅, H) Determines the Isomorphism Type of H}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{17:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.17},
  URN =		{urn:nbn:de:0030-drops-117022},
  doi =		{10.4230/LIPIcs.ITCS.2020.17},
  annote =	{Keywords: Graph homomorphism, Partition function, Complexity dichotomy, Connection matrices and tensors}
}
  • Refine by Author
  • 1 Cai, Jin-Yi
  • 1 Coulson, Matthew
  • 1 Davies, Ewan
  • 1 Govorov, Artem
  • 1 Kolla, Alexandra
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Approximation algorithms
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Algorithm design techniques
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 Complexity dichotomy
  • 1 Connection matrices and tensors
  • 1 Graph homomorphism
  • 1 Partition function
  • 1 Potts model
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 2 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact