Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHow to Play Unique Games on Expanders
175
0
0.0
(
0
)
Added by
Yury Makarychev
Publication date
2009
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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 algorithm finds an assignment satisfying at least a $1- C varepsilon/h_G$ fraction of all constraints if $varepsilon < c lambda_G$ where $h_G$ is the edge expansion of $G$, $lambda_G$ is the second smallest eigenvalue of the Laplacian of $G$, and $C$ and $c$ are some absolute constants.
rate research
Read More
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 Unique Games, then she chooses an epsilon-fraction of all edges, and finally replaces (corrupts) the constraints corresponding to these edges with new constraints. If all steps are adversarial, the adversary can obtain any (1-epsilon) satisfiable instance, so then the problem is as hard as in the worst case. In our semi-random model, one of the steps is random, and all other steps are adversarial. We show that known algorithms for unique games (in particular, all algorithms that use the standard SDP relaxation) fail to solve semi-random instances of Unique Games. We present an algorithm that with high probability finds a solution satisfying a (1-delta) fraction of all constraints in semi-random instances (we require that the average degree of the graph is Omega(log k). To this end, we consider a new non-standard SDP program for Unique Games, which is not a relaxation for the problem, and show how to analyze it. We present a new rounding scheme that simultaneously uses SDP and LP solutions, which we believe is of independent interest. Our result holds only for epsilon less than some absolute constant. We prove that if epsilon > 1/2, then the problem is hard in one of the models, the result assumes the 2-to-2 conjecture. Finally, we study semi-random instances of Unique Games that are at most (1-epsilon) satisfiable. We present an algorithm that with high probability, distinguishes between the case when the instance is a semi-random instance and the case when the instance is an (arbitrary) (1-delta) satisfiable instance if epsilon > c delta.
We give an algorithm for solving unique games (UG) instances whenever low-degree sum-of-squares proofs certify good bounds on the small-set-expansion of the underlying constraint graph via a hypercontractive inequality. Our algorithm is in fact more versatile, and succeeds even when the constraint graph is not a small-set expander as long as the structure of non-expanding small sets is (informally speaking) characterized by a low-degree sum-of-squares proof. Our results are obtained by rounding emph{low-entropy} solutions -- measured via a new global potential function -- to sum-of-squares (SoS) semidefinite programs. This technique adds to the (currently short) list of general tools for analyzing SoS relaxations for emph{worst-case} optimization problems. As corollaries, we obtain the first polynomial-time algorithms for solving any UG instance where the constraint graph is either the emph{noisy hypercube}, the emph{short code} or the emph{Johnson} graph. The prior best algorithm for such instances was the eigenvalue enumeration algorithm of Arora, Barak, and Steurer (2010) which requires quasi-polynomial time for the noisy hypercube and nearly-exponential time for the short code and Johnson graphs. All of our results achieve an approximation of $1-epsilon$ vs $delta$ for UG instances, where $epsilon>0$ and $delta > 0$ depend on the expansion parameters of the graph but are independent of the alphabet size.
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.
Higher order random walks (HD-walks) on high dimensional expanders (HDX) have seen an incredible amount of study and application since their introduction by Kaufman and Mass [KM16], yet their broader combinatorial and spectral properties remain poorly understood. We develop a combinatorial characterization of the spectral structure of HD-walks on two-sided local-spectral expanders [DK17], which offer a broad generalization of the well-studied Johnson and Grassmann graphs. Our characterization, which shows that the spectra of HD-walks lie tightly concentrated in a few combinatorially structured strips, leads to novel structural theorems such as a tight $ell_2$-characterization of edge-expansion, as well as to a new understanding of local-to-global algorithms on HDX. Towards the latter, we introduce a spectral complexity measure called Stripped Threshold Rank, and show how it can replace the (much larger) threshold rank in controlling the performance of algorithms on structured objects. Combined with a sum-of-squares proof of the former $ell_2$-characterization, we give a concrete application of this framework to algorithms for unique games on HD-walks, in many cases improving the state of the art [RBS11, ABS15] from nearly-exponential to polynomial time (e.g. for sparsifications of Johnson graphs or of slices of the $q$-ary hypercube). Our characterization of expansion also holds an interesting connection to hardness of approximation, where an $ell_infty$-variant for the Grassmann graphs was recently used to resolve the 2-2 Games Conjecture [KMS18]. We give a reduction from a related $ell_infty$-variant to our $ell_2$-characterization, but it loses factors in the regime of interest for hardness where the gap between $ell_2$ and $ell_infty$ structure is large. Nevertheless, we open the door for further work on the use of HDX in hardness of approximation and unique games.
Deterministic constructions of expander graphs have been an important topic of research in computer science and mathematics, with many well-studied constructions of infinite families of expanders. In some applications, though, an infinite family is not enough: we need expanders which are close to each other. We study the following question: Construct an an infinite sequence of expanders $G_0,G_1,dots$, such that for every two consecutive graphs $G_i$ and $G_{i+1}$, $G_{i+1}$ can be obtained from $G_i$ by adding a single vertex and inserting/removing a small number of edges, which we call the expansion cost of transitioning from $G_i$ to $G_{i+1}$. This question is very natural, e.g., in the context of datacenter networks, where the vertices represent racks of servers, and the expansion cost captures the amount of rewiring needed when adding another rack to the network. We present an explicit construction of $d$-regular expanders with expansion cost at most $5d/2$, for any $dgeq 6$. Our construction leverages the notion of a 2-lift of a graph. This operation was first analyzed by Bilu and Linial, who repeatedly applied 2-lifts to construct an infinite family of expanders which double in size from one expander to the next. Our construction can be viewed as a way to interpolate between Bilu-Linial expanders with low expansion cost while preserving good edge expansion throughout. While our main motivation is centralized (datacenter networks), we also get the best-known distributed expander construction in the self-healing model.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
