اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدComputational topology and the Unique Games Conjecture
297
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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 and the Unique Games Conjecture. Our starting point is Linials 2005 observation that the only known problems whose inapproximability is equivalent to the Unique Games Conjecture - Unique Games and Max-2Lin - are instances of Maximum Section of a Covering Space on graphs. We then observe that the reduction between these two problems (Khot-Kindler-Mossel-ODonnell, FOCS 2004; SICOMP, 2007) gives a well-defined map of covering spaces. We further prove that inapproximability for Maximum Section of a Covering Space on (cell decompositions of) closed 2-manifolds is also equivalent to the Unique Games Conjecture. This gives the first new Unique Games-complete problem in over a decade. Our results partially settle an open question of Chen and Freedman (SODA 2010; Disc. Comput. Geom., 2011) from computational topology, by showing that their question is almost equivalent to the Unique Games Conjecture. (The main difference is that they ask for inapproximability over $mathbb{Z}/2mathbb{Z}$, and we show Unique Games-completeness over $mathbb{Z}/kmathbb{Z}$ for large $k$.) This equivalence comes from the fact that when the structure group $G$ of the covering space is Abelian - or more generally for principal $G$-bundles - Maximum Section of a $G$-Covering Space is the same as the well-studied problem of 1-Homology Localization. Although our most technically demanding result is an application of Unique Games to computational topology, we hope that our observations on the topological nature of the Unique Games Conjecture will lead to applications of algebraic topology to the Unique Games Conjecture in the future.
قيم البحث
اقرأ أيضاً
Recently, a standardized framework was proposed for introducing quantum-inspired moves in mathematical games with perfect information and no chance. The beauty of quantum games-succinct in representation, rich in structures, explosive in complexity,
dazzling for visualization, and sophisticated for strategic reasoning-has drawn us to play concrete games full of subtleties and to characterize abstract properties pertinent to complexity consequence. Going beyond individual games, we explore the tractability of quantum combinatorial games as whole, and address fundamental questions including: Quantum Leap in Complexity: Are there polynomial-time solvable games whose quantum extensions are intractable? Quantum Collapses in Complexity: Are there PSPACE-complete games whose quantum extensions fall to the lower levels of the polynomial-time hierarchy? Quantumness Matters: How do outcome classes and strategies change under quantum moves? Under what conditions doesnt quantumness matter? PSPACE Barrier for Quantum Leap: Can quantum moves launch PSPACE games into outer polynomial space We show that quantum moves not only enrich the game structure, but also impact their computational complexity. In settling some of these basic questions, we characterize both the powers and limitations of quantum moves as well as the superposition of game configurations that they create. Our constructive proofs-both on the leap of complexity in concrete Quantum Nim and Quantum Undirected Geography and on the continuous collapses, in the quantum setting, of complexity in abstract PSPACE-complete games to each level of the polynomial-time hierarchy-illustrate the striking computational landscape over quantum games and highlight surprising turns with unexpected quantum impact. Our studies also enable us to identify several elegant open questions fundamental to quantum combinatorial game theory (QCGT).
The long code is a central tool in hardness of approximation, especially in questions related to the unique games conjecture. We construct a new code that is exponentially more efficient, but can still be used in many of these applications. Using the
new code we obtain exponential improvements over several known results, including the following: 1. For any eps > 0, we show the existence of an n vertex graph G where every set of o(n) vertices has expansion 1 - eps, but Gs adjacency matrix has more than exp(log^delta n) eigenvalues larger than 1 - eps, where delta depends only on eps. This answers an open question of Arora, Barak and Steurer (FOCS 2010) who asked whether one can improve over the noise graph on the Boolean hypercube that has poly(log n) such eigenvalues. 2. A gadget that reduces unique games instances with linear constraints modulo K into instances with alphabet k with a blowup of K^polylog(K), improving over the previously known gadget with blowup of 2^K. 3. An n variable integrality gap for Unique Games that that survives exp(poly(log log n)) rounds of the SDP + Sherali Adams hierarchy, improving on the previously known bound of poly(log log n). We show a connection between the local testability of linear codes and small set expansion in certain related Cayley graphs, and use this connection to derandomize the noise graph on the Boolean hypercube.
Computers are known to solve a wide spectrum of problems, however not all problems are computationally solvable. Further, the solvable problems themselves vary on the amount of computational resources they require for being solved. The rigorous analy
sis of problems and assigning them to complexity classes what makes up the immense field of complexity theory. Do protein folding and sudoku have something in common? It might not seem so but complexity theory tells us that if we had an algorithm that could solve sudoku efficiently then we could adapt it to predict for protein folding. This same property is held by classic platformer games such as Super Mario Bros, which was proven to be NP-complete by Erik Demaine et. al. This article attempts to review the analysis of classical platformer games. Here, we explore the field of complexity theory through a broad survey of literature and then use it to prove that that solving a generalized level in the game Celeste is NP-complete. Later, we also show how a small change in it makes the game presumably harder to compute. Various abstractions and formalisms related to modelling of games in general (namely game theory and constraint logic) and 2D platformer video games, including the generalized meta-theorems originally formulated by Giovanni Viglietta are also presented.
We give a new algorithm for Unique Games which is based on purely {em spectral} techniques, in contrast to previous work in the area, which relies heavily on semidefinite programming (SDP). Given a highly satisfiable instance of Unique Games, our alg
orithm is able to recover a good assignment. The approximation guarantee depends only on the completeness of the game, and not on the alphabet size, while the running time depends on spectral properties of the {em Label-Extended} graph associated with the instance of Unique Games. We further show that on input the integrality gap instance of Khot and Vishnoi, our algorithm runs in quasi-polynomial time and decides that the instance if highly unsatisfiable. Notably, when run on this instance, the standard SDP relaxation of Unique Games {em fails}. As a special case, we also re-derive a polynomial time algorithm for Unique Games on expander constraint graphs. The main ingredient of our algorithm is a technique to effectively use the full spectrum of the underlying graph instead of just the second eigenvalue, which is of independent interest. The question of how to take advantage of the full spectrum of a graph in the design of algorithms has been often studied, but no significant progress was made prior to this work.
We study the problem of approximating the value of a Unique Game instance in the streaming model. A simple count of the number of constraints divided by $p$, the alphabet size of the Unique Game, gives a trivial $p$-approximation that can be computed
in $O(log n)$ space. Meanwhile, with high probability, a sample of $tilde{O}(n)$ constraints suffices to estimate the optimal value to $(1+epsilon)$ accuracy. We prove that any single-pass streaming algorithm that achieves a $(p-epsilon)$-approximation requires $Omega_epsilon(sqrt{n})$ space. Our proof is via a reduction from lower bounds for a communication problem that is a $p$-ary variant of the Boolean Hidden Matching problem studied in the literature. Given the utility of Unique Games as a starting point for reduction to other optimization problems, our strong hardness for approximating Unique Games could lead to downemph{stream} hardness results for streaming approximability for other CSP-like problems.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
