ﻻ يوجد ملخص باللغة العربية
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 refute the Unique Games Conjecture.
In this paper, we study the average case complexity of the Unique Games problem. We propose a natural semi-random model, in which a unique game instance is generated in several steps. First an adversary selects a completely satisfiable instance of Un
In this note we improve a recent result by Arora, Khot, Kolla, Steurer, Tulsiani, and Vishnoi on solving the Unique Games problem on expanders. Given a $(1-varepsilon)$-satisfiable instance of Unique Games with the constraint graph $G$, our algorit
This entry in the Encyclopedia of Complexity and Systems Science, Springer present a summary of some of the concepts and calculational tools that have been developed in attempts to apply statistical physics approaches to seismology. We summarize the
Covering spaces of graphs have long been useful for studying expanders (as graph lifts) and unique games (as the label-extended graph). In this paper we advocate for the thesis that there is a much deeper relationship between computational topology a
}We study (vertex-disjoint) $P_2$-packings in graphs under a parameterized perspective. Starting from a maximal $P_2$-packing $p$ of size $j$ we use extremal arguments for determining how many vertices of $p$ appear in some $P_2$-packing of size $(j+