A 2-prover game is called unique if the answer of one prover uniquely determines second and vice versa (we implicitly assume games to be round games). The value a maximum acceptance probability verifier over all strategies. We make following conjecture regarding power games, which we call Unique Games Conjecture:(MATH) Conjecture: For arbitrarily small constants $ \ \zeta, \delta > 0$, there exists constant $k = k(\zeta,\delta)$ such that it NP-hard determine whether with answers from domain...

In this paper we show a reduction from the Unique Games problem to of approximating MAX‐CUT within factor $\alpha_{\text{\tiny{GW}}} + \epsilon$ for all $\epsilon > 0$; here \approx .878567$ denotes approximation ratio achieved by algorithm Goemans and Williamson in [J. Assoc. Comput. Mach., 42 (1995), pp. 1115–1145]. This implies that if Conjecture Khot [Proceedings 34th Annual ACM Symposium on Theory Computing, 2002, 767–775] holds, then Goemans–Williamson is optimal. Our result indicates...

In this paper, we disprove the following conjecture due to Goemans (1997) and Linial (2002): "Every negative type metric embeds into with constant distortion." We show that for every /spl delta/ > 0, large enough n, there is an n-point which requires distortion at-least (log log n) /sup 1/6-/spl delta// embed l/sub 1/. Surprisingly, our construction inspired by Unique Games Conjecture (UGC) of Khot (2002), establishing a previously unsuspected connection between PCPs theory embeddings. first...

Assuming that NP $\not\subseteq$ $\cap_{\epsilon > 0}$ BPTIME($2^{n^\epsilon}$), we show graph min‐bisection, dense k‐subgraph, and bipartite clique have no polynomial time approximation scheme (PTAS). We give a reduction from the minimum distance of code (MDC) problem. Starting with an instance MDC, build quasi‐random probabilistically checkable proof (PCP) suffices to prove desired inapproximability results. In PCP, query pattern verifier looks random in certain precise sense. Among...

Let p > 1 be any fixed real. We show that assuming NP ⊈ RP, there is no polynomial time algorithm approximates the Shortest Vector Problem (SVP) in ℓ norm within a constant factor. Under stronger assumption RTIME(2 poly (log n ) ), we polynomial-time with approximation ratio 2 1/2−ϵ where dimension of lattice and ϵ 0 an arbitrarily small constant.We first give new (randomized) reduction from Closest (CVP) to SVP achieves some factor hardness. The based on BCH Codes. Its advantage...

The author presents improved inapproximability results for three problems: the problem of finding maximum clique size in a graph, chromatic number and coloring graph with small colors. J. Hastad's (1996) result shows that n vertices is inapproximable polynomial time within factor n/sup 1-/spl epsi// or arbitrarily constant /spl epsi/>0 unless NP=ZPP. We aim at getting best subconstant value epsi/ result. prove n/2((log n))/sup 1-y/ corresponding to epsi/=1/(log n)/sup gamma// some gamma/>0...

We study the communication complexity of set disjointness problem in general multiparty model. For t players, each holding a subset universe size n, we establish near-optimal lower bound /spl Omega/(n/(t log t)) on determining whether their sets are disjoint. In more restrictive one-way model, which players required to speak predetermined order, improve our an optimal Omega/(n/t). These results upon earlier bounds Omega/(n/t/sup 2/) and Omega/((/spl epsiv//sup 2/n)/t/sup 1+/spl epsiv//) due...

We address well-studied problems concerning the learn-ability of parities and halfspaces in presence classification noise. Learning under uniform distribution with random noise, also called noisy parity problem is a famous open computational learning. reduce number basic regarding learning to parities. show that distribution, adversarial noise reduces Together algorithm Blum et al. (2003), this gives first nontrivial for DNF expressions just logarithmic variables. k-juntas k These reductions...

Given a k-uniform hypergraph, the Ek-Vertex-Cover problem is to find smallest subset of vertices that intersects every hyperedge. We present new multilayered probabilistically checkable proof (PCP) construction extends Raz verifier. This enables us prove NP-hard approximate within factor $(k-1-\epsilon)$ for arbitrary constants $\epsilon>0$ and $k\ge 3$. The result nearly tight as this can be easily approximated k. Our makes use biased long-code analyzed using combinatorial properties s-wise...

Assuming that NP /spl nsube//spl cap//sub epsi/> 0/ BPTIME(2/sup n/spl epsi//), we show graph min-bisection, densest subgraph and bipartite clique have no PTAS. We give a reduction from the minimum distance of code problem (MDC). Starting with an instance MDC, build quasi-random PCP suffices to prove desired inapproximability results. In PCP, query pattern verifier looks random in some precise sense. Among several new techniques introduced, way certifying given polynomial belongs subspace...

In this paper, we give evidence suggesting that MAX-CUT is NP-hard to approximate within a factor of /spl alpha//sub cw/+ epsi/, for all epsi/ > 0, where cw/ denotes the approximation ratio achieved by Goemans-Williamson algorithm (1995). ap/ .878567. This result conditional, relying on two conjectures: a) unique games conjecture Khot; and, b) very believable call majority stablest conjecture. These results indicate geometric nature might be intrinsic problem. The same conjectures also imply...

We present an efficient algorithm to find a good solution the Unique Games problem when constraint graph is expander.

For arbitrarily small constants epsilon, delta ¿.¿ > 0, we present a long code test with one free bit, completeness 1-epsilon and soundness delta. Using the test, prove following two inapproximability results:1. Assuming Unique Games Conjecture of Khot, given an n-vertex graph that has disjoint independent sets size (1/2-¿)n each, it is NP-hard to find set n.2. (new) stronger version Conjecture, scheduling problem minimizing weighted completion time precedence constraints inapproximable...

In this article, we disprove a conjecture of Goemans and Linial; namely, that every negative type metric embeds into ℓ 1 with constant distortion. We show for an arbitrarily small δ > 0, all large enough n , there is -point which requires distortion at least (log log ) 1/6-δ to embed . Surprisingly, our construction inspired by the Unique Games Conjecture (UGC), establishing previously unsuspected connection between probabilistically checkable proof systems (PCPs) theory embeddings. first...

We present a candidate reduction from the 3-Lin problem to 2-to-2 Games and combinatorial hypothesis about Grassmann graphs which, if correct, is sufficient show soundness of in certain non-standard sense. A that sound this sense implies it NP-hard distinguish whether an n-vertex graph has independent set size ( 1- 1/√2 ) n - o(n) or every o(n), consequently, approximate Vertex Cover within factor √2-o(1).

We present a polynomial time reduction from gap-3LIN to label cover with 2-to-1 constraints. In the "yes" case fraction of satisfied constraints is at least 1 −ε, and in "no" we show that this most ε, assuming certain (new) combinatorial hypothesis on Grassmann graph. other words, describe implies conjecture imperfect completeness. The companion submitted paper [Dinur, Khot, Kindler, Minzer Safra, STOC 2018] makes some progress towards proving hypothesis.

Arora, Rao and Vazirani [2] showed that the standard semi-definite programming (SDP) relaxation of Sparsest Cut problem with triangle inequality constraints has an integrality gap O(√log n). They conjectured is bounded from above by a constant. In this paper, we disprove conjecture (referred to as ARV-Conjecture) constructing Ω(log log n) instance. Khot Vishnoi [16] had earlier disproved non-uniform version ARV-Conjecture.A simple "stretching" instance for serves SDP Minimum Linear...

Based on a conjecture regarding the power of unique 2-prover-1-round games presented in [S. Khot, (2002)], we show that vertex cover is hard to approximate within any constant factor better than 2. We actually stronger result, namely, based same conjecture, k-uniform hypergraphs k.

This article surveys recently discovered connections between the Unique Games Conjecture and computational complexity, algorithms, discrete Fourier analysis, geometry.

We study the learnability of several fundamental concept classes in agnostic learning framework [D. Haussler, Inform. and Comput., 100 (1992), pp. 78–150] [M. Kearns, R. Schapire, L. Sellie, Machine Learning, 17 (1994), 115–141]. show that under uniform distribution, agnostically parities reduce to with random classification noise, commonly referred as noisy parity problem. Together algorithm [A. Blum, A. Kalai, H. Wasserman, J. ACM, 50 (2003), 506–519], this gives first nontrivial for...