Let G be a k-player game with value <1, whose query distribution is such that no marginal on k-1 players admits a non-trivial Abelian embedding. We show that for every n>=N, the value of the n-fold parallel repetition of G is val(G^n) <= 1/(log log ... log n), where the number of logarithms is C, and N=N(G) and 1 <= C <= k^(O(k)) are constants. As a consequence, we obtain a parallel repetition theorem for all 3-player games whose query distribution is pairwise-connected. Prior to our work, only inverse Ackermann decay bounds were known for such games.

Abstract. We show that the value of the [Formula: see text]-fold repeated GHZ game is at most [Formula: see text], improving upon the polynomial bound established by Holmgren and Raz. Our result is established via a reduction to approximate subgroup-type questions from additive combinatorics.

We study linearity testing over the p-biased hypercube ({0,1}ⁿ, μ_p^{⊗n}) in the 1% regime. For a distribution ν supported over {x ∈ {0,1}^k:∑_{i=1}^k x_i = 0 (mod 2)}, with marginal distribution μ_p in each coordinate, the corresponding k-query linearity test Lin(ν) proceeds as follows: Given query access to a function f:{0,1}ⁿ → {-1,1}, sample (x_1,… ,x_k)∼ ν^{⊗n}, query f on x_1,… ,x_k, and accept if and only if ∏_{i ∈ [k]} f(x_i) = 1. Building on the work of Bhangale, Khot, and Minzer (STOC '23), we show, for 0 < p ≤ 1/2, that if k ≥ 1+1/p, then there exists a distribution ν such that the test Lin(ν) works in the 1% regime; that is, any function f:{0,1}ⁿ → {-1,1} passing the test Lin(ν) with probability ≥ 1/2+ε, for some constant ε > 0, satisfies Pr_{x∼μ_p^{⊗n}}[f(x) = g(x)] ≥ 1/2+δ, for some linear function g, and a constant δ = δ(ε) > 0. Conversely, we show that if k < 1+1/p, then no such test Lin(ν) works in the 1% regime. Our key observation is that the linearity test Lin(ν) works if and only if the distribution ν satisfies a certain pairwise independence property.

The problem of studying k-wise correlations in product spaces, i.e., correlations of the form ${\mathbb{E}_{\left( {{x_1}, \ldots ,{x_k}} \right)\sim \mu \otimes n}}\left[ {{f_1}\left( {{x_1}} \right) \cdots f\left( {{x_k}} \right)} \right]$ where ${\text{ }}{f_i}:\sum\nolimits_i^n \to \mathbb{C}$ are all 1-bounded functions and µ is a distribution over Σ1× … × Σk, appears in many different contexts throughout discrete mathematics. Examples include additive combinatorics, extremal combinatorics, hardness of approximation and probability. The goal in an inverse theorem is to characterize the type of functions f1,…,fkthat achieve non-trivial correlations, under minimal assumptions on the distribution µ.We give new inverse theorems for k-wise correlations for all k ⩾ 3. For k = 3, our inverse theorem works for any distribution µ which is pairwise-connected, which is essentially the minimal assumption required for a nontrivial inverse theorem to hold. For k > 3, our inverse theorem applies for distributions µ satisfying the stronger condition of not having any Abelian embeddings. This resolves a conjecture from [Bhangale-Khot-Minzer, STOC 2022].We give applications of our inverse theorems to additive combinatorics, hardness of approximation, and property testing. First, we show that there exists c > 0 such that any set A ⊆ {0,1,2}nwith density at least Ω((loglogloglogn)−c) must contain a combinatorial line, i.e., x,y,z ∈ {0,1,2}n, not all equal, such that xi= yi= zior (xi,yi,zi) = (0,1,2) for all i = 1,2,…,n. In other words, we give "reasonable bounds" for the density Hales-Jewett theorem of length 3. This involves combining our inverse theorems with several additional insights, motivated by Shkredov’s proof of the corners theorem and Polymath’s combinatorial proof of the density Hales-Jewett theorem. Second, we show how to construct a dictatorship vs quasi-random test that has perfect completeness and soundness s + ε from integrality gap instances with similar parameters, provided that its local distributions have no Abelian embeddings. Third, we analyze the direct-sum tester of [Dinur-Golubev, RANDOM 2019] in the low-soundness regime.

The Gap Exponential Time Hypothesis rules out FPT algorithms providing (nearly) tight inapproximability results for a host of fundamental problems in parameterized complexity. One of the downsides of working under Gap-ETH is that the assumption is not inherently in the parameterized complexity world, and therefore one of the main research directions is to replace Gap-ETH with weaker assumptions.

STOC ’25, Prague, Czechia

Abstract We consider the $$P$$ P -CSP problem for 3-ary predicates $$P$$ P on satisfiable instances. We show that under certain conditions on $$P$$ P and a $$(1,s)$$ ( 1 , s ) integrality gap instance of the $$P$$ P -CSP problem, it can be translated into a dictatorship vs. quasirandomness test with perfect completeness and soundness $$s+\epsilon$$ s + ϵ , for every constant $$\epsilon>0$$ ϵ > 0 . Compared to Ragahvendra (in: Proceedings of the fortieth annual ACM symposium on theory of computing (STOC), pp 245–254, 2008), we do not lose perfect completeness. This is particularly interesting as this test implies new hardness results on satisfiable constraint satisfaction problems, assuming the Rich 2-to-1 Games Conjecture by Braverman et al. (in: Lee JR (ed) Volume 185 of Leibniz international proceedings in informatics (LIPIcs), 27:1–27:20. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, 2021b. https://drops.dagstuhl.de/opus/volltexte/2021/13566 ).Our result can be seen as the first step of a potentially long-term challenging program of characterizing optimal inapproximability of every satisfiable $$k$$ k -ary CSP. At the heart of the reduction is our main analytical lemma for a class of 3-ary predicates, which is a generalization of a lemma by Mossel (Geom Funct Anal 19(6):1713–1756, 2010). The lemma and a further generalization of it that we conjecture may be of independent interest.

We prove a stability result for general 3-wise correlations over distributions satisfying mild connectivity properties. More concretely, we show that if Σ,Γ and Φ are alphabets of constant size, and µ is a distribution over Σ×Γ×Φ satisfying: (1) the probability of each atom is at least Ω(1), (2) µ is pairwise connected, and (3) µ has no Abelian embeddings into (ℤ,+), then the following holds. Any triplets of 1-bounded functions f∶ Σn→ℂ, g∶ Γn→ℂ, h∶ Φn→ℂ satisfying

We show that the value of the n-fold repeated GHZ game is at most $2^{-\Omega(n)}$, improving upon the polynomial bound established by Holmgren and Raz. Our result is established via a reduction to approximate subgroup type questions from additive combinatorics.

Let Σ be an alphabet and µ be a distribution on Σk for some k ≥ 2. Let α > 0 be the minimum probability of a tuple in the support of µ (denoted supp(µ)). Here, the support of µ is the set of all tuples in Σk that have a positive probability mass under µ. We treat the parameters Σ, k, µ, α as fixed and constant.

In this paper we study functions on the Boolean hypercube that have the property that after applying certain random restrictions, the restricted function is correlated to a linear function with non-negligible probability. If the given function is correlated with a linear function then this property clearly holds. Furthermore, the property also holds for low-degree functions as low-degree functions become a constant function under a random restriction with a non-negligible probability. We show that this essentially is the only possible reason. More specifically, we show that the function must be correlated to a product of a linear function and a low-degree function. One of the main motivations of studying this question comes from the recent work of the authors towards understanding approximability of satisfiable Constraint Satisfaction Problems.

We consider the P-CSP problem for 3-ary predicates P on satisfiable instances. We show that under certain conditions on P and a (1,s) integrality gap instance of the P-CSP problem, it can be translated into a dictatorship vs. quasirandomness test with perfect completeness and soundness s+ε, for every constant ε>0. Compared to Ragahvendra’s result [STOC, 2008], we do not lose perfect completeness. This is particularly interesting as this test implies new hardness results on satisfiable constraint satisfaction problems, assuming the Rich 2-to-1 Games Conjecture by Braverman, Khot, and Minzer [ITCS, 2021]. Our result can be seen as the first step of a potentially long-term challenging program of characterizing optimal inapproximability of every satisfiable k-ary CSP.

Given an alphabet size$m\in\mathbb{N}$thought of as a constant, and$\vec{k}=(k_{1}, \ldots, k_{m})$whose entries sum of up$n$, the$\vec{k}$-multi-slice is the set of vectors$x\in[m]^{n}$in which each symbol$i\in[m]$appears precisely$k_{i}$times. We show an invariance principle for low-degree functions over the multi-slice, to functions over the product space ($[m]^{n}, \mu^{n}$) in which$\mu(i)=k_{i}/n$. This answers a question raised by [21]. As applications of the invariance principle, we show: 1)An analogue of the “dictatorship test implies computational hardness” paradigm for problems with perfect completeness, for a certain class of dictatorship tests. Our computational hardness is proved assuming a recent strengthening of the Unique-Games Conjecture, called the Rich 2-to-1 Games Conjecture. Using this analogue, we show that assuming the Rich 2-to-1 Games Conjecture, (a) there is an$r$-ary CSP$\mathcal{P}_{r}$for which it is NP-hard to distinguish satisfiable instances of the CSP and instances that are at most$\frac{2r+1}{2^{r}}+o(1)$satisfiable, and (b) hardness of distinguishing 3-colorable graphs, and graphs that do not contain an independent set of size$o(1)$. 2)A reduction of the problem of studying expectations of products of functions on the multi-slice to studying expectations of products of functions on correlated, product spaces. In particular, we are able to deduce analogues of the Gaussian bounds from [38] for the multi-slice. 3)In a companion paper, we show further applications of our invariance principle in extremal combinatorics, and more specifically to proving removal lemmas of a wide family of hypergraphs$H$called$\zeta$-forests, which is a natural extension of the well-studied case of matchings.

We propose a variant of the 2-to-1 Games Conjecture that we call the Rich 2-to-1 Games Conjecture and show that it is equivalent to the Unique Games Conjecture. We are motivated by two considerations. Firstly, in light of the recent proof of the 2-to-1 Games Conjecture [Subhash Khot et al., 2017; Irit Dinur et al., 2018; Irit Dinur et al., 2018; Subhash Khot et al., 2018], we hope to understand how one might make further progress towards a proof of the Unique Games Conjecture. Secondly, the new variant along with perfect completeness in addition, might imply hardness of approximation results that necessarily require perfect completeness and (hence) are not implied by the Unique Games Conjecture.

We give alternate proofs for three related results in analysis of Boolean functions, namely the KKL Theorem, Friedgut’s Junta Theorem, and Talagrand’s strengthening of the KKL Theorem. We follow a new approach: looking at the first Fourier level of the function after a suitable random restriction and applying the Log-Sobolev inequality appropriately. In particular, we avoid using the hypercontractive inequality that is common to the original proofs. Our proofs might serve as an alternate, uniform exposition to these theorems and the techniques might benefit further research.

A seminal result of Håstad (2001) shows that it is NP-hard to find an assignment that satisfies 1/|G|+ε fraction of the constraints of a given k-LIN instance over an abelian group, even if there is an assignment that satisfies (1−ε) fraction of the constraints, for any constant ε>0. Engebretsen, Holmerin and Russell (2004) later showed that the same hardness result holds for k-LIN instances over any finite non-abelian group.

A systematic study of simultaneous optimization of constraint satisfaction problems was initiated by Bhangale et al. [ICALP, 2015]. The simplest such problem is the simultaneous Max-Cut. Bhangale et al. [SODA, 2018] gave a .878-minimum approximation algorithm for simultaneous Max-Cut which is almost optimal assuming the Unique Games Conjecture (UGC). For single instance Max-Cut, Goemans-Williamson [JACM, 1995] gave an α_GW-approximation algorithm where α_GW ≈ .87856720... which is optimal assuming the UGC. It was left open whether one can achieve an α_GW-minimum approximation algorithm for simultaneous Max-Cut. We answer the question by showing that there exists an absolute constant ε₀ ≥ 10^{-5} such that it is NP-hard to get an (α_GW- ε₀)-minimum approximation for simultaneous Max-Cut assuming the Unique Games Conjecture.

We prove that for every constant c and epsilon = (log n)^{-c}, there is no polynomial time algorithm that when given an instance of 3-LIN with n variables where an (1 - epsilon)-fraction of the clauses are satisfiable, finds an assignment that satisfies atleast (1/2 + epsilon)-fraction of clauses unless NP subseteq BPP. The previous best hardness using a polynomial time reduction achieves epsilon = (log log n)^{-c}, which is obtained by the Label Cover hardness of Moshkovitz and Raz [J. ACM, 57(5), 2010] followed by the reduction from Label Cover to 3-LIN of Håstad [J. ACM, 48(4):798 - 859, 2001]. Our main idea is to prove a hardness result for Label Cover similar to Moshkovitz and Raz where each projection has a linear structure. This linear structure of Label Cover allows us to use Hadamard codes instead of long codes, making the reduction more efficient. For the hardness of Linear Label Cover, we follow the work of Dinur and Harsha [SIAM J. Comput., 42(6):2452 - 2486, 2013] that simplified the construction of Moshkovitz and Raz, and observe that running their reduction from a hardness of the problem LIN (of unbounded arity) instead of the more standard problem of solving quadratic equations ensures the linearity of the resultant Label Cover.

The 2-to-2 Games Theorem of [Subhash Khot et al., 2017; Dinur et al., 2018; Dinur et al., 2018; Dinur et al., 2018] implies that it is NP-hard to distinguish between Unique Games instances with assignment satisfying at least (1/2-epsilon) fraction of the constraints vs. no assignment satisfying more than epsilon fraction of the constraints, for every constant epsilon>0. We show that the reduction can be transformed in a non-trivial way to give a stronger guarantee in the completeness case: For at least (1/2-epsilon) fraction of the vertices on one side, all the constraints associated with them in the Unique Games instance can be satisfied. We use this guarantee to convert the known UG-hardness results to NP-hardness. We show: 1) Tight inapproximability of approximating independent sets in degree d graphs within a factor of Omega(d/(log^2 d)), where d is a constant. 2) NP-hardness of approximate the Maximum Acyclic Subgraph problem within a factor of 2/3+epsilon, improving the previous ratio of 14/15+epsilon by Austrin et al. [Austrin et al., 2015]. 3) For any predicate P^{-1}(1) subseteq [q]^k supporting a balanced pairwise independent distribution, given a P-CSP instance with value at least 1/2-epsilon, it is NP-hard to satisfy more than (|P^{-1}(1)|/(q^k))+epsilon fraction of constraints.

Andoni, Krauthgamer and Razenshteyn (AKR) proved (STOC’15) that a finite-dimensional normed space (X, ‖·‖x) admits a O(1) sketching algorithm (namely, with O(1) sketch size and O(1) approximation) if and only if for every ε ∊ (0, 1) there exist α  1 and an embedding f : X → ℓ1–ε such that ‖x – y‖x  ‖f(x) – f(y)‖1–ε  α‖x – y‖x for all x, y ∊ X. The “if part” of this theorem follows from a sketching algorithm of Indyk (FOCS 2000). The contribution of AKR is therefore to demonstrate that the mere availability of a sketching algorithm implies the existence of the aforementioned geometric realization. Indyk's algorithm shows that the “if part” of the AKR characterization holds true for any metric space whatsoever, i.e., the existence of an embedding as above implies sketchability even when X is not a normed space. Due to this, a natural question that AKR posed was whether the assumption that the underlying space is a normed space is needed for their characterization of sketchability. We resolve this question by proving that for arbitrarily large n ∊ ℕ there is an n-point metric space (M(n), dM(n)) which is O(1)-sketchable yet for every ε ∊ (0, ψ), if α(n)  1 and fn : M(n) → ℓ1–ε are such that dM(n)(x, y)  ‖fn(x) – fn(y)‖1–ε  α(n)dM(n)(x, y) for all x, y ∊ M(n), then necessarily limn→∞ α(n) = ∞.

We prove that pseudorandom sets in the Grassmann graph have near-perfect expansion. This completes the last missing piece of the proof of the 2-to-2-Games Conjecture (albeit with imperfect completeness). The Grassmann graph has induced subgraphs that are themselves isomorphic to Grassmann graphs of lower orders. A set of vertices is called pseudorandom if its density within all such subgraphs (of constant order) is at most slightly higher than its density in the entire graph. We prove that pseudorandom sets have almost no edges within them. Namely, their edge-expansion is very close to 1.

In the simultaneous Max-Cut problem, we are given k weighted graphs on the same set of n vertices, and the goal is to find a cut of the vertex set so that the minimum, over the k graphs, of the cut value is as large as possible. Previous work [BKS15] gave a polynomial time algorithm which achieved an approximation factor of 1/2 – o(1) for this problem (and an approximation factor of 1/2 + εk in the unweighted case, where εk → 0 as k → ∞). In this work, we give a polynomial time approximation algorithm for simultaneous Max-Cut with an approximation factor of 0.8780 (for all constant k). The natural SDP formulation for simultaneous Max-Cut was shown to have an integrality gap of 1/2 + εk in [BKS15]. In achieving the better approximation guarantee, we use a stronger Sum-of-Squares hierarchy SDP relaxation and a rounding algorithm based on Raghavendra-Tan [RT12], in addition to techniques from [BKS15].

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

We show a directed and robust analogue of a boolean isoperimetric-type theorem of Talagrand [ Geom. Funct. Anal., 3 (1993), pp. 295--314]. As an application, we give a monotonicity testing algorithm that makes $\tilde{O}(\sqrt{n}/\varepsilon^2)$ nonadaptive queries to a function $f:\{0,1\}^n \mapsto \{0,1\}$, always accepts a monotone function, and rejects a function that is $\varepsilon$-far from being monotone with constant probability.

A Boolean function f:{0,1}^n\->{0,1} is called a dictator if it depends on exactly one variable i.e f(x_1, x_2, ..., x_n) = x_i for some i in [n]. In this work, we study a k-query dictatorship test. Dictatorship tests are central in proving many hardness results for constraint satisfaction problems. The dictatorship test is said to have perfect completeness if it accepts any dictator function. The soundness of a test is the maximum probability with which it accepts any function far from a dictator. Our main result is a k-query dictatorship test with perfect completeness and soundness (2k + 1)/(2^k), where k is of the form 2^t -1 for any integer t > 2. This improves upon the result of [Tamaki-Yoshida, Random Structures & Algorithms, 2015] which gave a dictatorship test with soundness (2k + 3)/(2^k).

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

We show that it is quasi-NP-hard to color 2-colorable 12-uniform hypergraphs with $2^{(\log n)^{\Omega(1) }}$ colors where $n$ is the number of vertices. Previously, Guruswami Harsha, H\aa stad, Srinivasan, and Varma showed that it is quasi-NP-hard to color 2-colorable 8-uniform hypergraphs with $2^{2^{\Omega(\sqrt{\log \log n})}}$ colors. Their result is obtained by composing a standard outer probabilistically checkable proof (PCP) with an inner PCP based on the short code of superconstant degree. Our result is instead obtained by composing a new outer PCP with an inner PCP based on the short code of degree two.

We present an adaptive tester for the unateness property of Boolean functions. Given a function f:{0,1}^n -> {0,1} the tester makes O(n log(n)/epsilon) adaptive queries to the function. The tester always accepts a unate function, and rejects with probability at least 0.9 if a function is epsilon-far from being unate.

We study the natural problem of estimating the expansion of subsets of vertices on one side of a bipartite graph. More precisely, given a bipartite graph G(U,V,E) and a parameter beta, the goal is to find a subset V' subseteq V containing beta fraction of the vertices of V which minimizes the size of N(V'), the neighborhood of V'. This problem, which we call Bipartite Expansion, is a special case of submodular minimization subject to a cardinality constraint, and is also related to other problems in graph partitioning and expansion. Previous to this work, there was no hardness of approximation known for Bipartite Expansion. In this paper we show the following strong inapproximability for Bipartite Expansion: for any constants tau, gamma > 0 there is no algorithm which, given a constant beta > 0 and a bipartite graph G(U,V,E), runs in polynomial time and decides whether - (YES case) There is a subset S^* subseteq V s.t. |S^*| >= beta*|V| satisfying |N(S^*)| <= gamma |U|, or - (NO case) Any subset S subseteq V s.t. |S| >= tau*beta*|V| satisfies |N(S)| >= (1 - gamma)|U|, unless NP subseteq intersect_{epsilon > 0}{DTIME}(2^{n^epsi;on}) i.e. NP has subexponential time algorithms. We note that our hardness result stated above is a vertex expansion analogue of the Small Set (Edge) Expansion Conjecture of Raghavendra and Steurer 2010.

The talk will present connections between approximability of NP-complete problems, analysis, and geometry, and the role played by the Unique Games Conjecture in facilitating these connections.

In the Gap-clique (k, k/2) problem, the input is an n-vertex graph G, and the goal is to decide whether G contains a clique of size k or contains no clique of size k/2. It is an open question in the study of fixed parameterized tractability whether the Gap-clique (k, k/2) problem is fixed parameter tractable, i.e., whether it has an algorithm that runs in time f(k) ⋅ nα, where f(k) is an arbitrary function of the parameter k and the exponent α is a constant independent of k.

We propose a candidate reduction for ruling out polynomial-time algorithms for unique games, either under plausible complexity assumptions, or unconditionally for Lasserre semi-definite programs with a constant number of rounds. We analyze the completeness and Lasserre solution of our construction, and provide a soundness analysis in a certain setting of interest. Addressing general settings is tightly connected to a question on Gaussian isoperimetry. Our construction is based on our previous work on the complexity of approximately solving a system of linear equations over reals, which we suggested as an avenue towards a (positive) resolution of the Unique Games Conjecture. The construction employs a new encoding scheme that we call the real code. The real code has two useful properties: like the long code, it has a unique local test, and like the Hadamard code, it has the so-called sub-code covering property.

We show a directed and robust analogue of a boolean isoperimetric type theorem of Talagrand [13]. As an application, we give a monotonicity testing algorithm that makes O̅(√n/ε2) non-adaptive queries to a function f : {0, 1}n→ {0, 1}, always accepts a monotone function and rejects a function that is ε-far from being monotone with constant probability.

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 that for an arbitrarily small constant δ > 0, for all large enough n , there is an n -point negative type metric which requires distortion at least (log log n ) 1/6-δ to embed into ℓ 1 . Surprisingly, our construction is inspired by the Unique Games Conjecture (UGC), establishing a previously unsuspected connection between probabilistically checkable proof systems (PCPs) and the theory of metric embeddings. We first prove that the UGC implies a super-constant hardness result for the (nonuniform) S PARSEST C UT problem. Though this hardness result relies on the UGC, we demonstrate, nevertheless, that the corresponding PCP reduction can be used to construct an “integrality gap instance” for S PARSEST C UT . Towards this, we first construct an integrality gap instance for a natural SDP relaxation of U NIQUE G AMES . Then we “simulate” the PCP reduction and “translate” the integrality gap instance of U NIQUE G AMES to an integrality gap instance of S PARSEST C UT . This enables us to prove a (log log n ) 1/6-δ integrality gap for S PARSEST C UT , which is known to be equivalent to the metric embedding lower bound.

We show that it is quasi-NP-hard to color 2-colorable 12-uniform hypergraphs with 2(log n) O(1) colors where n is the number of vertices. Previously, Guruswami et al. [1] showed that it is quasi-NP-hard to color 2-colorable 8-uniform hypergraphs with 22 O(vlog log n) colors. Their result is obtained by composing a standard Outer PCP with an Inner PCP based on the Short Code of super-constant degree. Our result is instead obtained by composing a new Outer PCP with an Inner PCP based on the Short Code of degree two.

This work studies the hardness of finding independent sets in hypergraphs which are either 2-colorable or are almost 2-colorable, i.e. can be 2-colored after removing a small fraction of vertices and the incident hyperedges. To be precise, say that a hypergraph is (1 – ∊)-almost 2-colorable if removing an ∊ fraction of its vertices and all hyperedges incident on them makes the remaining hypergraph 2-colorable. In particular we prove the following results. For an arbitrarily small constant γ > 0, there is a constant ξ > 0, such that, given a 4-uniform hypergraph on n vertices which is (1 – ∊)-almost 2-colorable for , it is quasi-NP-hard1 to find an independent set of vertices. For any constants ∊, δ > 0, given as input a 3-uniform hypergraph on n vertices which is (1 – ∊)-almost 2-colorable, it is NP-hard to find an independent set of δn vertices. Assuming the d-to-1 Games Conjecture the following holds. For any constant δ > 0, given a 2-colorable 3-uniform hypergraph on n vertices, it is NP-hard to find an independent set of δn vertices. The hardness result on independent set in almost 2-colorable 3-uniform hypergraphs was earlier known only assuming the Unique Games Conjecture. In this work we prove the result unconditionally, combining Fourier analytic techniques with the Multi-Layered PCP of [11]. For independent sets in 2-colorable 3-uniform hypergaphs we prove the first strong hardness result, albeit assuming the d-to-1 Games Conjecture. Our reduction uses the d-to-1 Game as a starting point to construct a Multi-Layered PCP with the smoothness property. We use analytical techniques based on the Invariance Principle of Mossel [36]. The smoothness property is crucially exploited in a manner similar to recent work of Håstad [20] and Wenner [45]. Our result on almost 2-colorable 4-uniform hypergraphs gives the first nearly polynomial hardness factor for independent set in hypergraphs which are (almost) colorable with constantly many colors. It partially bridges the gap between the previous best lower bound of poly(logn) and the algorithmic upper bounds of nΩ(1). This also exhibits a bottleneck to improving the algorithmic techniques for hypergraph coloring.

For a predicate f: {-1, 1}k ↦ {0, 1} with ρ(f) = |f-1(1)|/2k, we call the predicate strongly approximation resistant if given a near-satisfiable instance of CSP(f), it is computationally hard to find an assignment such that the fraction of constraints satisfied is outside the range [ρ(f) - Ω(1), ρ(f) + Ω(1)].

We prove that for an arbitrarily small constant $\varepsilon>0,$ the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor $2^{\log ^{1-\varepsilon}n}$, under the assumption that NP $\not \subseteq$ SIZE$(2^{\log^{O(1/\varepsilon)} n})$.

We present a simple deterministic gap-preserving reduction from SAT to the minimum distance of code problem over F2. We also show how to extend the reduction to work over any fixed finite field. Previously, a randomized reduction was known due to Dumer, Micciancio, and Sudan, which was recently derandomized by Cheng and Wan. These reductions rely on highly nontrivial coding theoretic constructions, whereas our reduction is elementary. As an additional feature, our reduction gives hardness within a constant factor even for asymptotically good codes, i.e., having constant positive rate and relative distance. Previously, it was not known how to achieve a deterministic reduction for such codes.

Constraint satisfaction problems are some of the most well-studied NP-hard problems, 3SAT being a prominent example. It is known by Hastad's 1997 result that 3SAT is "approximation resistant" in the following sense: given a near-satisfiable instance, a trivial algorithm that assigns random boolean values to the variables satisfies 7/8 fraction of the constraints and no efficient algorithm can do strictly better unless P=NP! 3SAT is a CSP that corresponds to the ternary OR predicate. In general, a CSP has constraints given by some fixed predicate P:{0,1}^k -> {True, False} (on possibly negated variables) and the predicate is called approximation resistant if, on a near-satisfiable instance, it is computationally hard to perform strictly better than a random assignment. The quest to understand approximation resistance has played a central role in the theory of probabilistically checkable proofs (PCPs) and hardness of approximation. This talk will give a survey of the topic, including recent work giving a complete characterization of approximation resistance (i.e. a necessary and sufficient condition on the predicate that makes the corresponding CSP approximation resistant).

A constraint satisfaction problem (CSP) is said to be approximation resistant if it is hard to approximate better than the trivial algorithm which picks a uniformly random assignment. Assuming the Unique Games Conjecture, we give a characterization of approximation resistance for k-partite CSPs defined by an even predicate.

We construct a PCP based on the hyper-graph linearity test with 3 free queries. It has near-perfect completeness and soundness strictly less than 1/8. Such a PCP was known before only assuming the Unique Games Conjecture, albeit with soundness arbitrarily close to 1/16. At a technical level, our main contribution is constructing a new outer PCP which is "robust" against bounded degree polynomials, and showing that it can be composed with the hyper-graph linearity test with 3 free queries. We believe this outer PCP may be useful in obtaining the optimal query vs. soundness tradeoff for PCPs.

In this paper, we consider the problem of approximately solving a system of homogeneous linear equations over reals, where each equation contains at most three variables. Since the all-zero assignment always satisfies all the equations exactly, we restrict the assignments to be “nontrivial.” Here is an informal statement of our result: it is $\mathcal{NP}$-hard to distinguish whether there is a nontrivial assignment that satisfies $1-\delta$ fraction of the equations or every nontrivial assignment fails to satisfy a constant fraction of the equations with a “margin” of $\Omega(\sqrt{\delta})$. We develop linearity and dictatorship testing procedures for functions $f: \mathbb{R}^n \mapsto \mathbb{R}$ over a Gaussian space, which could be of independent interest. Our research is motivated by a possible approach to proving the unique games conjecture.

We show that for any ε >; 0, and positive integers k and q such that q ≥ 2k+ 1, given a graph on N vertices that has a q-colorable induced subgraph of (1 - ε)N vertices, it is NP-hard to find an independent set of N/qk+1vertices. This substantially improves upon the work of Dinur et al. [1] who gave a corresponding bound of N/q2. Our result implies that for any positive integer k, given a graph that has an independent set of ≈ (2k+ 1)-1fraction of vertices, it is NP-hard to find an independent set of (2k+ 1)-(k+1)fraction of vertices. This improves on the previous work of Engebretsen and Holmerin [2] who proved a gap of ≈ 2-kvs 2-(k:2), which is best possible using techniques (including those of [2]) based on the query efficient PCP of Samorodnitsky and Trevisan [3].

We prove that for an arbitrarily small constant ε>0, assuming NP⊈ DTIME (2logO 1-ε n), the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor better than 2log1-ε n. This improves upon the previous hardness factor of (log n)δ for some δ>0 due to [AKKV05].

We show that for any fixed prime q ≥ 5 and constant ζ >; 0, it is NP-hard to distinguish whether a two prover one round game with q6answers has value at least 1 - ζ or at most 4/q. The result is obtained by combining two techniques: (i) An Inner PCP based on the point versus subspace test for linear functions. The test is analyzed Fourier analytically, (ii) The Outer/Inner PCP composition that relies on a certain sub-code covering property for Hadamard codes. This is a new and essentially black-box method to translate a codeword test for Hadamard codes to a consistency test, leading to a full PCP construction. As an application, we show that unless NP has quasi-polynomial time deterministic algorithms, the Quadratic Programming Problem is inapproximable within factor (log n)1/6-o(1).

In this paper, we consider the problem of approximately solving a system of homogeneous linear equations over reals, where each equation contains at most three variables.

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

For every ∈ > 0, and integer q ≥ 3, we show that given an N-vertex graph that has an induced q-colorable subgraph of size (1 - ∈)N, it is NP-hard to find an independent set of size N/q2.

In the kernel clustering problem we are given a (large) n × n symmetric positive semidefinite matrix A = (aij) with and a (small) k × k symmetric positive semidefinite matrix B = (bij). The goal is to find a partition {S1, …, Sk} of {1, … n} which maximizes . We design a polynomial time approximation algorithm that achieves an approximation ratio of , where R(B) and C(B) are geometric parameters that depend only on the matrix B, defined as follows: if bij = 〈vi, vj〉 is the Gram matrix representation of B for some v1, …, vk ∊ ℝk then R(B) is the minimum radius of a Euclidean ball containing the points {v1, …, vk}. The parameter C(B) is defined as the maximum over all measurable partitions {A1, …, Ak} of ℝk–1 of the quantity , where for i ∊ {1, …, k} the vector zi ∊ ℝk–1 is the Gaussian moment of Ai, i.e., . We also show that for every ε > 0, achieving an approximation guarantee of is Unique Games hard.

We study the polynomial reconstruction problem for low-degree multivariate polynomials over finite field $\mathbb{F}[2]$. In this problem, we are given a set of points $\mathbf{x}\in\{0,1\}^n$ and target values $f(\mathbf{x})\in\{0,1\}$ for each of these points, with the promise that there is a polynomial over $\mathbb{F}[2]$ of degree at most d that agrees with f at $1-\varepsilon$ fraction of the points. Our goal is to find a degree d polynomial that has good agreement with f. We show that it is NP-hard to find a polynomial that agrees with f on more than $1-2^{-d}+\delta$ fraction of the points for any $\epsilon,\delta>0$. This holds even with the stronger promise that the polynomial that fits the data is in fact linear, whereas the algorithm is allowed to find a polynomial of degree d. Previously the only known hardness of approximation (or even NP-completeness) was for the case when $d =1$, which follows from a celebrated result of Håstad [J. ACM, 48 (2001), pp. 798–859]. In the setting of Computational Learning, our result shows the hardness of nonproper agnostic learning of parities, where the learner is allowed a low-degree polynomial over $\mathbb{F}[2]$ as a hypothesis. This is the first nonproper hardness result for this central problem in computational learning. Our results can be extended to multivariate polynomial reconstruction over any finite field.

We study the inapproximability of Vertex Cover and Independent Set on degree d graphs. We prove that: (1) Vertex Cover is Unique Games-hard to approximate to within a factor 2 - (2 + od(1)) log log d/log d. This exactly matches the algorithmic result of Halperin up to the od(1) term. (2) Independent Set is Unique Games-hard to approximate to within a factor O(d/log2d). This improves the d/logO(1)(d)) Unique Games hardness result of Samorodnitsky and Trevisan. Additionally, our result does not rely on the construction of a query efficient PCP as in.

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, we prove the following two inapproximability results:1. Assuming the Unique Games Conjecture of Khot, given an n-vertex graph that has two disjoint independent sets of size (1/2-¿)n each, it is NP-hard to find an independent set of size delta n.2. Assuming a (new) stronger version of the Unique Games Conjecture, the scheduling problem of minimizing weighted completion time with precedence constraints is inapproximable within factor 2-¿.

We construct integrality gap instances for SDP relaxation of the MAXIMUM CUT and the SPARSEST CUT problems. If the triangle inequality constraints are added to the SDP, then the SDP vectors naturally define an n-point negative type metric where n is the number of vertices in the problem instance. Our gap-instances satisfy a stronger constraint that every sub-metric on t = O((log log log n)1/6) points is isometrically embeddable into l1. The local l1-embeddability constraints are implied when the basic SDP relaxation is augmented with t rounds of the Sherali-Adams LP-relaxation. For the MAXIMUM CUT problem, we obtain an optimal gap of αGW-1- ϵ, where αGWis the Goemans-Williamson constant [11] and ϵ ≫ 0 is an arbitrarily small constant. For the SPARSEST CUT problem, we obtain a gap of Ω((log log log n)1/13). The latter result can be rephrased as a construction of an npoint negative type metric such that every t-point sub-metric is isometrically l1-embeddable, but embedding the whole metric into l1incurs distortion Ω((log log log n)1/13).

We study the learnability of several fundamental concept classes in the agnostic learning framework of [D. Haussler, Inform. and Comput., 100 (1992), pp. 78–150] and [M. Kearns, R. Schapire, and L. Sellie, Machine Learning, 17 (1994), pp. 115–141]. We show that under the uniform distribution, agnostically learning parities reduce to learning parities with random classification noise, commonly referred to as the noisy parity problem. Together with the parity learning algorithm of [A. Blum, A. Kalai, and H. Wasserman, J. ACM, 50 (2003), pp. 506–519], this gives the first nontrivial algorithm for agnostic learning of parities. We use similar techniques to reduce learning of two other fundamental concept classes under the uniform distribution to learning of noisy parities. Namely, we show that learning of disjunctive normal form (DNF) expressions reduces to learning noisy parities of just logarithmic number of variables, and learning of k-juntas reduces to learning noisy parities of k variables. We give essentially optimal hardness results for agnostic learning of monomials over $\{0,1\}^n$ and halfspaces over $\mathbb{Q}^n$. We show that for any constant $\epsilon$ finding a monomial (halfspace) that agrees with an unknown function on $1/2+\epsilon$ fraction of the examples is NP-hard even when there exists a monomial (halfspace) that agrees with the unknown function on $1-\epsilon$ fraction of the examples. This resolves an open question due to Blum and significantly improves on a number of previous hardness results for these problems. We extend these results to $\epsilon=2^{-\log^{1-\lambda}n}$ ($\epsilon=2^{-\sqrt{\log n}}$ in the case of halfspaces) for any constant $\lambda>0$ under stronger complexity assumptions.

We study the fundamental classification problems 0-Extension and Metric Labeling. A generalization of Multiway Cut, 0-Extension is closely related to partitioning problems in graph theory and to Lipschitz extensions in Banach spaces; its generalization Metric Labeling is motivated by applications in computer vision. Researchers had proposed using earthmover metrics to get polynomial–time-solvable relaxations for these problems. A conjecture that has attracted much attention recently is that the integrality ratio for these relaxations is constant. We prove (1) that the integrality ratio of the earthmover relaxation for Metric Labeling is $\Omega(\log k)$ (which is asymptotically tight), k being the number of labels, whereas the best previous lower bound on the integrality ratio was only constant; (2) that the integrality ratio of the earthmover relaxation for 0-Extension is $\Omega(\sqrt{\log k})$, k being the number of terminals (it was known to be $O((\log k)/\log\log k)$), whereas the best previous lower bound was only constant; (3) that for no $\epsilon>0$ is there a polynomial-time $O((\log n)^{1/4-\epsilon})$-approximation algorithm for 0-Extension, n being the number of vertices, unless NP$\subseteq$DTIME$(n^{\mathrm{poly}(\log n)})$, whereas the strongest inapproximability result known before was only MAX SNP-hardness; and (4) that there is a polynomial-time approximation algorithm for 0-Extension with performance ratio $O(\sqrt{\mathrm{diam}(d)})$, where $\mathrm{diam}(d)$ is the ratio of the largest to smallest nonzero distances in the terminal metric.

In the kernel clustering problem we are given a large ntimesn positive semi-definite matrix A=(aij) with Sigmai,jn=1 aij=0 and a small ktimesk positivesemi-definite matrix B=bij. The goal is to find a partition S1,..Skof {1,...n} which maximizes the quantity Sigmai,j=1k(Sigma(i,j)isinSitimesSj). We study the computational complexity of this generic clustering problem which originates in the theory of machine learning. We design a constant factor polynomial time approximation algorithm forthis problem, answering a question posed by Song, Smola, Gretton and Borgwardt. In some cases we manage to compute the sharp approximation threshold for this problem assuming the unique games conjecture (UGC). In particular, when B is the 3times3 identity matrix the UGC hardness threshold of this problem is exactly 16pi/27. We present and study a geometricconjecture of independent interest which we show would imply thatthe UGC threshold when B is the ktimesk identity matrix is 8pi/9(1-1/k) for every kges3.

We study the problem of finding the minimum size DNF formula for a function f : {0, 1}drarr {0,1} given its truth table. We show that unless NP sube DTIME(npoly(logn)), there is no polynomial time algorithm that approximates this problem to within factor d1-epsivwhere epsiv > 0 is an arbitrarily small constant. Our result essentially matches the known O(d) approximation for the problem. We also study weak learnability of small size DNF formulas. We show that assuming NP sube RP, for arbitrarily small constant epsiv > 0 and any fixed positive integer t, a two term DNF cannot be PAC-learnt in polynomial time by a t term DNF to within 1/2 + epsiv accuracy. Under the same complexity assumption, we show that for arbitrarily small constants mu, epsiv > 0 and any fixed positive integer t, an AND function (i.e. a single term DNF) cannot be PAC-learnt in polynomial time under adversarial mu-noise by a t-CNF to within 1/2 + epsiv accuracy.

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

We show that unless NP = RP, it is hard to (even) weakly PAC-learn intersection of two halfspaces in Rn using a hypothesis which is a function of up to l linear threshold functions for any integer l. Specifically, we show that for every integer l and an arbitrarily small constant ε > 0, unless NP = RP, no polynomial time algorithm can distinguish whether there is an intersection of two halfspaces that correctly classifies a given set of labeled points in Rn, or whether any function of l linear threshold functions can correctly classify at most 1/2+ε fraction of the points.

We design a randomized polynomial time algorithm which, given a 3-tensor of real numbers $A=\{a_{ijk}\}_{i,j,k=1}^n$ such that for all $i,j,k\in\{1,\dots,n\}$ we have $a_{ijk}=a_{ikj}=a_{kji}=a_{jik}=a_{kij}=a_{jki}$ and $a_{iik}=a_{ijj}=a_{iji}=0$, computes a number $\operatorname{Alg}(A)$ which satisfies with probability at least $\frac12$, $\Omega(\sqrt{\frac{\log n}{n}}t)\cdot\max_{x\in \{-1,1\}^n}\sum_{i,j,k=1}^n a_{ijk}x_ix_jx_k\le\operatorname{Alg}(A)\le\max_{x\in \{-1,1\}^n}\sum_{i,j,k=1}^n a_{ijk}x_ix_jx_k$. On the other hand, we show via a simple reduction from a result of Håstad and Venkatesh [Random Structures Algorithms, 25 (2004), pp. 117–149] that under the assumption $NP\not\subseteq DTIME(n^{(\log n)^{O(1)}})$, for every $\epsilon>0$ there is no algorithm that approximates $\max_{x\in \{-1,1\}^n}\sum_{i,j,k=1}^n a_{ijk}x_ix_jx_k$ within a factor of $2^{(\log n)^{1-\epsilon}}$ in time $2^{(\log n)^{O(1)}}$. Our algorithm is based on a reduction to the problem of computing the diameter of a convex body in $\mathbb{R}^n$ with respect to the $L_1$ norm. We show that it is possible to do so up to a multiplicative error of $O(\sqrt{\frac{n}{\log n}})$, while no randomized polynomial time algorithm can achieve accuracy $o(\sqrt{\frac{n}{\log n}})$. This resolves a question posed by Brieden et al. in [Mathematika, 48 (2001), pp. 63–105]. We apply our new algorithm to improve the algorithm of Håstad and Venkatesh for the Max-E3-Lin-2 problem. Given an overdetermined system $\mathcal{E}$ of N linear equations modulo 2 in $n\le N$ Boolean variables such that in each equation only three distinct variables appear, the goal is to approximate in polynomial time the maximum number of satisfiable equations in $\mathcal{E}$ minus $\frac{N}{2}$ (i.e., we subtract the expected number of satisfied equations in a random assignment). Håstad and Venkatesh obtained an algorithm which approximates this value up to a factor of $O(\sqrt{N})$. We obtain an $O(\sqrt{\frac{n}{\log n}})$ approximation algorithm. By relating this problem to the refutation problem for random $3-CNF$ formulas, we give evidence that obtaining a significant improvement over this approximation factor is likely to be difficult.

We study the polynomial reconstruction problem, for low-degree multivariate polynomials over F[2]. In this problem, we are given a set of points x epsi {0, 1}nand target values f(x) epsi {0, 1} for each of these points, with the promise that there is a polynomial over F[2] of degree at most d that agrees with f at 1 - epsiv fraction of the points. Our goal is to find agree d polynomial that has good-agreement with f. We show that it is NP-hard to find a polynomial that agrees with f on more than 1 - 2-d+ delta fraction of the points for any epsiv, delta > 0. This holds even with the stronger promise that the polynomial that fits the data is in fact linear, wherejis the algorithm is allowed to find a polynomial of degree d. Previously the only known, hardness of approximation (or even NP-completeness) was for the case when d = I, which follows from a celebrated result of Has tad. In the setting of computational learning, our result shows the hardness of (non-proper) agnostic learning of parities, where the learner is allowed, a low-degree polynomial over F[2] as a hypothesis. This is the first non-proper hardness result for this central problem in computational learning. Our results extend-to multivariate polynomial reconstruction over any finite field.

We design a randomized polynomial time algorithm which, given a 3-tensor of real numbers A={aijk}ij,k=1nsuch that for all i,j,kisin{1,...,n} we have aijk=aikj=akji=ajik=akij=akjiand aiik=aijj=aiji=0, computes a number Alg(A) which satisfies with probability at least 1/2, Omega(radic(logn/n))ldrmaxxisin{-1,1}nSigmai,j,k=1naijkxixjxklesAlg(A)lesmaxxisin{-1,1}nSigmai,j,k=1naijkxixjxk. On the other hand, we show via a simple reduction from a result of Hastad and Venkatesh that under the assumption NPnsubeDTIME(n(logn)O(1)),for every epsiv>0 there is no algorithm that approximates maxxisin{-1,1}nSigmai,j,k=1naijkxixjxkwithin a factor of 2(logn)t-epsivin time 2(logn)O(1). Our algorithm is based on a reduction to the problem of computing the diameter of a convex body in Rnwith respect to the L1norm. We show that it is possible to do so up to a multiplicative error of O(radic(n/logn)), while no randomized polynomial time algorithm can achieve accuracy O(radic(n/logn)). This resolves a question posed by Brieden, Gritzmann, Kantian, Klee, Lovasz and Simonos. We apply our new algorithm improve the algorithm of Hastad and Venkatesh or the Max-E3-Lin-2 problem. Given an over-determined system epsiv of N linear equations modulo 2 in nlesN Boolean variables, such that in each equation appear only three distinct variables, the goal is to approximate in polynomial time the maximum number of satisfiable equations in epsiv minus N/2 (i.e. we subtract the expected number of satisfied equations in a random assignment). Hastad and Venkatesh obtained an algorithm which approximates this value up to a factor of O(radicN). We obtain a O(radic(n/logn)) approximation algorithm. By relating this problem to the refutation problem for random 3-CNF formulas we give evidence that obtaining a significant improvement over this approximation factor is likely to be difficult.

In this paper we show a reduction from the Unique Games problem to the problem of approximating MAX‐CUT to within a factor of $\alpha_{\text{\tiny{GW}}} + \epsilon$ for all $\epsilon > 0$; here $\alpha_{\text{\tiny{GW}}} \approx .878567$ denotes the approximation ratio achieved by the algorithm of Goemans and Williamson in [J. Assoc. Comput. Mach., 42 (1995), pp. 1115–1145]. This implies that if the Unique Games Conjecture of Khot in [Proceedings of the 34th Annual ACM Symposium on Theory of Computing, 2002, pp. 767–775] holds, then the Goemans–Williamson approximation algorithm is optimal. Our result indicates that the geometric nature of the Goemans–Williamson algorithm might be intrinsic to the MAX‐CUT problem. Our reduction relies on a theorem we call Majority Is Stablest. This was introduced as a conjecture in the original version of this paper, and was subsequently confirmed in [E. Mossel, R. O’Donnell, and K. Oleszkiewicz, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005, pp. 21–30]. A stronger version of this conjecture called Plurality Is Stablest is still open, although [E. Mossel, R. O’Donnell, and K. Oleszkiewicz, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005, pp. 21–30] contains a proof of an asymptotic version of it. Our techniques extend to several other two‐variable constraint satisfaction problems. In particular, subject to the Unique Games Conjecture, we show tight or nearly tight hardness results for MAX‐2SAT, MAX‐q‐CUT, and MAX‐2LIN(q). For MAX‐2SAT we show approximation hardness up to a factor of roughly $.943$. This nearly matches the $.940$ approximation algorithm of Lewin, Livnat, and Zwick in [Proceedings of the 9th Annual Conference on Integer Programming and Combinatorial Optimization, Springer‐Verlag, Berlin, 2002, pp. 67–82]. Furthermore, we show that our .943... factor is actually tight for a slightly restricted version of MAX‐2SAT. For MAX‐q‐CUT we show a hardness factor which asymptotically (for large q) matches the approximation factor achieved by Frieze and Jerrum [Improved approximation algorithms for MAX k‐CUT and MAX BISECTION, in Integer Programming and Combinatorial Optimization, Springer‐Verlag, Berlin, pp. 1–13], namely $1 - 1/q + 2({\rm ln}\,q)/q^2$. For MAX‐2LIN(q) we show hardness of distinguishing between instances which are $(1-\epsilon)$‐satisfiable and those which are not even, roughly, $(q^{-\epsilon/2})$‐satisfiable. These parameters almost match those achieved by the recent algorithm of Charikar, Makarychev, and Makarychev [Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006, pp. 205–214]. The hardness result holds even for instances in which all equations are of the form $x_i - x_j = c$. At a more qualitative level, this result also implies that $1-\epsilon$ vs. ε hardness for MAX‐2LIN(q) is equivalent to the Unique Games Conjecture.

We study a very basic open problem regarding the PCP characterization of NP, namely, the power of PCPs with 3 non-adaptive queries and perfect completeness. The lowest soundness known till now for such a PCP is 6/8 + epsi given by a construction of Hastad (1997). However, Zwick (1998) shows that a 3-query non-adaptive PCP with perfect completeness cannot achieve soundness below 5/8. In this paper, we construct a 3-query non-adaptive PCP with perfect completeness and soundness 20/27 + epsi, which improves upon the previous best soundness of 6/8 + epsi. A standard reduction from PCPs to constraint satisfaction problems (CSPs) implies that it is NP-hard to tell if a Boolean CSP on 3-variables has a satisfying assignment or no assignment satisfies more than 20/27 + epsi fraction of the constraints. Our construction uses "biased long codes" introduced by Dinur and Safra (2002). We develop new 3-query tests to check consistency between such codes. These tests are analyzed by extending Hastad's Fourier methods (1997) to the biased case

We address well-studied problems concerning the learn-ability of parities and halfspaces in the presence of classification noise. Learning of parities under the uniform distribution with random classification noise, also called the noisy parity problem is a famous open problem in computational learning. We reduce a number of basic problems regarding learning under the uniform distribution to learning of noisy parities. We show that under the uniform distribution, learning parities with adversarial classification noise reduces to learning parities with random classification noise. Together with the parity learning algorithm of Blum et al. (2003), this gives the first nontrivial algorithm for learning parities with adversarial noise. We show that learning of DNF expressions reduces to learning noisy parities of just logarithmic number of variables. We show that learning of k-juntas reduces to learning noisy parities of k variables. These reductions work even in the presence of random classification noise in the original DNF or junta. We then consider the problem of learning halfspaces over Qopfnwith adversarial noise or finding a halfspace that maximizes the agreement rate with a given set of examples. We prove an essentially optimal hardness factor of 2 - epsi, improving the factor of (85/84) - epsi due to Bshouty and Burroughs (2002). Finally, we show that majorities of halfspaces are hard to PAC-learn using any representation, based on the cryptographic assumption underlying the Ajtai-Dwork cryptosystem

Given a graph with maximum cut of (fractional) size c, the Goemans-Williamson semidefinite programming (SDP) algorithm by M. Goemans and D. Williamson (1995) is guaranteed to find a cut of size .878 middot c. However this guarantee becomes trivial when c is near frac12, since a random cut has expected size frac12. Recently, M. Charikar and K. Worth (2004) (analyzing an algorithm of U. Feige and G. Langberg (2001)) showed that given a graph with maximum cut frac12 + epsiv, one can find a cut of size frac12 + Omega(epsiv/ log(1/epsiv)). The main contribution of our paper is twofold: 1. We give a natural frac12 + epsiv vs. frac12 + O(epsiv/ log(1/epsiv)) SDP gap for MAXCUT in Gaussian space. This shows that the SDP-rounding algorithm of Charikar-Worth is essentially best possible. Further, the "s-linear rounding functions" used in the works of M. Charikar and K. Worth (2004) and U. Freige and M. Langberg (2001) arise as optimizers in our analysis, somewhat confirming a suggestion of U. Freige and M. Langberg (2001). 2. We show how this SDP gap can be translated into a long code test with the same parameters. This implies that beating the Charikar-Worth guarantee with any efficient algorithm is NP-hard, assuming the unique games conjecture (UGC) by S. Khot (2002). We view this result as essentially settling the approximability of MAXCUT, assuming UGC. Building on (1) we show how "randomness reduction" on related SDP gaps for the QUADRATICPROGRAMMING programming problem lets us make the Omega(log(1/epsiv)) gap as large as Omega(log n) for n-vertex graphs. In addition to optimally answering an open question of N. Alen et al. (2006), this technique may prove useful for other SDP gap problems. Finally, illustrating the generality of our technique in (2), we also show how to translate Reeds's SDP gap by J. Reeds (1993) for the Grothendieck Inequality into a UGC-hardness result for computing the par middot parinfin rarr 1norm of a matrix

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

We study the fundamental classification problems O-EXTENSION and METRIC LABELING. MINIMUM WEIGHT TRIANGULATION is closely related to partitioning problems in graph theory and to Lipschitz extensions in Banach spaces; its generalization METRIC LABELING is motivated by applications in computer vision. Researchers had proposed using earthmover metrics to get polynomial time-solvable relaxations for these problems. A conjecture that has attracted much attention recently is that the integrality ratio for these relaxations is constant.We prove

Assuming that NP $\not\subseteq$ $\cap_{\epsilon > 0}$ BPTIME($2^{n^\epsilon}$), we show that 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 of MDC, we build a quasi‐random probabilistically checkable proof (PCP) that suffices to prove the desired inapproximability results. In a quasi‐random PCP, the query pattern of the verifier looks random in a certain precise sense. Among the several new techniques we introduce, the most interesting one gives a way of certifying that a given polynomial belongs to a given linear subspace of polynomials. As is important for our purpose, the certificate itself happens to be another polynomial, and it can be checked probabilistically by reading a constant number of its values.

We study the complexity of approximating Max NM-E3SAT, a variant of Max 3SAT when the instances are guaranteed to not have any mixed clauses, i.e., every clause has either all its literals unnegated or all of them negated. This is a natural special case of Max 3SAT introduced Guruswami (2004), where the question of whether this variant can be approximated within a factor better than 7/8 was also posed. We prove that it is NP-hard to approximate Max NM-E3SAT within a factor of 7/8 + /spl epsiv/ for arbitrary /spl epsiv/ > 0, and thus this variant is no easier to approximate than general Max 3SAT. The proof uses the technique of multilayered PCPs, introduced by Dinur et al. (2003), to avoid the technical requirement of folding of the proof tables. Circumventing this requirement means that the PCP verifier can use the bits it accesses without additional negations, and this leads to a hardness for Max 3SAT without any mixed clauses.

We show that, unless NP/spl sube/DTIME(2/sup poly log(n)/) the closest vector problem with pre-processing, for /spl lscr//sub p/ norm for any p /spl ges/ 1, is hard to approximate within a factor of (log n)/sup 1/p - /spl epsi//' /P for any /spl epsi/ > 0. This improves the previous best factor of 3/sup 1/p/ - /spl epsi/ due to Regev (2004). Our results also imply that under the same complexity assumption, the nearest codeword problem with pre-processing is hard to approximate within a factor of (log n)/sup 1 - /spl epsi//' for any /spl epsi/ > 0.

Summary form only given. The discovery of the PCP theorem in 1992 led to an avalanche of hardness of approximation results, i.e. results showing that for certain NP hard optimization problems, computing even approximate solutions is hard. However, for many fundamental problems, obtaining satisfactory hardness results seems out of reach of current techniques. The unique games conjecture (UGC) was proposed in 2002 as an approach towards settling some of these open problems. A 2-Prover-1-Round game is called unique if for every answer of either prover, there is exactly one answer of the other prover if the verifier is to accept. The UGC states that for every constant /spl epsiv/ > 0, it is NP hard to distinguish whether the optimal strategy of provers in a unique 2P1R game has acceptance probability at least 1 - /spl epsiv/ or at most /spl epsiv/. The answer size k = k(/spl epsiv/) could be an arbitrary function of /spl epsiv/. The UGC has been shown to imply optimal hardness results for vertex cover and MAX-CUT problems, and superconstant hardness results for sparsest cut and Min-2SAT-Deletion problems. A variation of the conjecture has been shown to imply hardness of coloring 3-colorable graphs with constantly many colors. Apart from these applications to hardness results, the UGC has led to important (unconditional) results in Fourier analysis, the theory of metric embeddings, and integrality gap results for semidefinite programming relaxations. The tutorial aims to give an overview of the UGC, its applications, and attempts to prove or disprove it.

Various new nonembeddability results (mainly into L/sub 1/) are proved via Fourier analysis. In particular, it is shown that the edit distance on {0, 1}/sup d/ has L/sub 1/ distortion (log d)/sup 1/2 - o(1)/. We also give new lower bounds on the L/sub 1/ distortion of quotients of the discrete hypercube under group actions, and the transportation cost (Earthmover) metric.

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, and for large enough n, there is an n-point negative type metric which requires distortion at-least (log log n) /sup 1/6-/spl delta// to embed into l/sub 1/. Surprisingly, our construction is inspired by the Unique Games Conjecture (UGC) of Khot (2002), establishing a previously unsuspected connection between PCPs and the theory of metric embeddings. We first prove that the UGC implies super-constant hardness results for (non-uniform) sparsest cut and minimum uncut problems. It is already known that the UGC also implies an optimal hardness result for maximum cut (2004). Though these hardness results depend on the UGC, the integrality gap instances rely "only" on the PCP reductions for the respective problems. Towards this, we first construct an integrality gap instance for a natural SDP relaxation of unique games. Then, we "simulate" the PCP reduction and "translate"the integrality gap instance of unique games to integrality gap instances for the respective cut problems! This enables us to prove a (log log n) /sup 1/6-/spl delta// integrality gap for (nonuniform) sparsest cut and minimum uncut, and an optimal integrality gap for maximum cut. All our SDP solutions satisfy the so-called "triangle inequality" constraints. This also shows, for the first time, that the triangle inequality constraints do not add any power to the Goemans-Williamson's SDP relaxation of maximum cut. The integrality gap for sparsest cut immediately implies a lower bound for embedding negative type metrics into l/sub i/. It also disproves the non-uniform version of Arora, Rao and Vazirani's Conjecture (2004), asserting that the integrality gap of the sparsest cut SDP, with the triangle inequality constraints, is bounded from above by a constant.

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

Given a k-uniform hypergraph, the Ek-Vertex-Cover problem is to find the smallest subset of vertices that intersects every hyperedge. We present a new multilayered probabilistically checkable proof (PCP) construction that extends the Raz verifier. This enables us to prove that Ek-Vertex-Cover is NP-hard to approximate within a factor of $(k-1-\epsilon)$ for arbitrary constants $\epsilon>0$ and $k\ge 3$. The result is nearly tight as this problem can be easily approximated within factor k. Our construction makes use of the biased long-code and is analyzed using combinatorial properties of s-wise t-intersecting families of subsets. We also give a different proof that shows an inapproximability factor of $\lfloor \frac{k}{2} \rfloor -\eps$. In addition to being simpler, this proof also works for superconstant values of k up to (log N) 1/c , where c > 1 is a fixed constant and N is the number of hyperedges.

Let p > 1 be any fixed real. We show that assuming NP /spl nsube/ RP, it is hard to approximate the shortest vector problem (SVP) in l/sub p/ norm within an arbitrarily large constant factor. Under the stronger assumption NP /spl nsube/ RTIME(2/sup poly(log n)/), we show that the problem is hard to approximate within factor 2/sup log n1/2 - /spl epsi// where n is the dimension of the lattice and /spl epsi/> 0 is an arbitrarily small constant. This greatly improves all previous results in l/sub p/ norms with 1 < p < /spl infin/. The best results so far gave only a constant factor hardness, namely, 2/sup 1/p/ - /spl epsi/ by Micciancio and p/sup 1 - /spl epsi// in high l/sub p/ norms by Khot. We first give a new (randomized) reduction from closest vector problem (CVP) to SVP that achieves some constant factor hardness. The reduction is based on BCH codes. Its advantage is that the SVP instances produced by the reduction behave well under the augmented tensor product, a new variant of tensor product that we introduce. This enables us to boost the hardness factor to 2/sup log n1/2-/spl epsi//.

Assuming that NP /spl nsube//spl cap//sub /spl epsi/> 0/ BPTIME(2/sup n/spl epsi//), we show that 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 of MDC, we build a quasi-random PCP that suffices to prove the desired inapproximability results. In a quasi-random PCP, the query pattern of the verifier looks random in some precise sense. Among the several new techniques introduced, we give a way of certifying that a given polynomial belongs to a given subspace of polynomials. As is important for our purpose, the certificate itself happens to be another polynomial and it can be checked by reading a constant number of its values.

In this paper, we give evidence suggesting that MAX-CUT is NP-hard to approximate to within a factor of /spl alpha//sub cw/+ /spl epsi/, for all /spl epsi/ > 0, where /spl alpha//sub cw/ denotes the approximation ratio achieved by the Goemans-Williamson algorithm (1995). /spl alpha//sub cw/ /spl ap/ .878567. This result is conditional, relying on two conjectures: a) the unique games conjecture of Khot; and, b) a very believable conjecture we call the majority is stablest conjecture. These results indicate that the geometric nature of the Goemans-Williamson algorithm might be intrinsic to the MAX-CUT problem. The same two conjectures also imply that it is NP-hard to (/spl beta/ + /spl epsi/)-approximate MAX-2SAT, where /spl beta/ /spl ap/ .943943 is the minimum of (2 + (2//spl pi/) /spl theta/)/(3 - cos(/spl theta/)) on (/spl pi//2, /spl pi/). Motivated by our proof techniques, we show that if the MAX-2CSP and MAX-2SAT problems are slightly restricted - in a way that seems to retain all their hardness -then they have (/spl alpha//sub GW/-/spl epsi/)- and (/spl beta/ - /spl epsi/)-approximation algorithms, respectively. Though we are unable to prove the majority is stablest conjecture, we give some partial results and indicate possible directions of attack. Our partial results are enough to imply that MAX-CUT is hard to (3/4 + 1/(2/spl pi/) + /spl epsi/)-approximate (/spl ap/ .909155), assuming only the unique games conjecture. We also discuss MAX-2CSP problems over non-Boolean domains and state some related results and conjectures. We show, for example, that the unique games conjecture implies that it is hard to approximate MAX-2LIN(q) to within any constant factor.

We show an optimal hardness result for the following problem: Given a system of homogeneous linear equations over GF(2) with 3 variables per equation, find a balanced assignment that satisfies maximum number of equations. For arbitrarily small constant ζ > 0, we show that it is hard to determine (in polynomial time) whether such a system has a balanced assignment that satisfies 1-ζ fraction of equations or there is no balanced assignment that satisfies more than ½+ζ fraction of equations. As a corollary, we show that it is hard to approximate (in polynomial time) the Max-Bisection problem within factor 16⁄15-ζ. These hardness results hold under the assumption NP ⊈ ∩ε > 0 DTIME(2nε).Our results are obtained via a construction of a new PCP outer verifier that has a mixing property and a smoothness property. These properties are crucial in the analysis of the inner verifier. No previous outer verifier can achieve both these properties simultaneously. An outer verifier is essentially a 2-query PCP over a large alphabet. Loosely speaking, the mixing property says that the locations of the two queries read by the verifier are uncorrelated. The smoothness property says that the verifier's acceptance predicate is close to being a bijective predicate. Our construction relies on the algebraic techniques used to prove the PCP Theorem. This is in contrast with all earlier constructions that use the PCP Theorem as a black-box. The progress in inapproximability theory seems to require new ideas for building outer verifiers and our construction takes a first step in that direction.

We study the communication complexity of the set disjointness problem in the general multiparty model. For t players, each holding a subset of a universe of size n, we establish a near-optimal lower bound of /spl Omega/(n/(t log t)) on the communication complexity of the problem of determining whether their sets are disjoint. In the more restrictive one-way communication model, in which the players are required to speak in a predetermined order, we improve our bound to an optimal /spl Omega/(n/t). These results improve upon the earlier bounds of /spl Omega/(n/t/sup 2/) in the general model, and /spl Omega/((/spl epsiv//sup 2/n)/t/sup 1+/spl epsiv//) in the one-way model, due to Bar-Yossef, Jayram, Kumar, and Sivakumar (2002). As in the case of earlier results, our bounds apply to the unique intersection promise problem. This communication problem is known to have connections with the space complexity of approximating frequency moments in the data stream model. Our results lead to an improved space complexity lower bound of /spl Omega/(n/sup 1-2/k//log n) for approximating the k/sup th/ frequency moment with a constant number of passes over the input, and a technical improvement to /spl Omega/(n/sup 1-2/k/) if only one pass over the input is permitted. Our proofs rely on the information theoretic direct sum decomposition paradigm of Bar-Yossef et al. [2002]. Our improvements stem from novel analytical techniques, as opposed to earlier techniques based on Hellinger and related distances, for estimating the information cost of protocols for one-bit functions.

As a problem with similar properties to minimum bisection, we consider the following: given a homogeneous system of linear equations over Z/sub 2/, with exactly k variables in each equation, find a balanced assignment that minimizes the number of satisfied equations. A balanced assignment is one which contains an equal number of 0s and 1s. When k=2, this is the minimum bisection problem. We consider the case k=3. In this case, it is NP-complete to determine whether the object function is zero [U. Feige, (2003)], so the problem is not approximable at all. However, we prove that it is NP-hard to determine distinguish between the cases that all but a fraction /spl epsi/ of the equations can be satisfied and that at least a fraction 1/4-/spl epsi/ of all equations cannot be satisfied. A similar result for minimum bisection would imply that the problem is hard to approximate within any constant. For the problem of approximating the maximum number of equations satisfied by a balanced assignment, this implies that the problem is NP-hard to approximate within 4/3-/spl epsi/, for any /spl epsi/>0.

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 show a stronger result, namely, based on the same conjecture, vertex cover on k-uniform hypergraphs is hard to approximate within any constant factor better than k.

We show that for every /spl epsi/ > 0, there is a constant p(/spl epsi/) such that for all integers p /spl ges/ p(/spl epsi/), it is NP-hard to approximate the shortest vector problem in L/sub p/ norm within factor p/sup 1 - /spl epsi// under randomized reductions. For large values of p, this improves the factor 2/sup 1/p/ - /spl delta/ hardness shown by D. Micciancio (1998).

Given a k-uniform hyper-graph, the Ek-Vertex-Cover problem is to find the smallest subset of vertices that intersects every hyper-edge. We present a new multilayered PCP construction that extends the Raz verifier. This enables us to prove that Ek-Vertex-Cover is NP-hard to approximate within factor (k-1-ε) for any k ≥ 3 and any ε>0. The result is essentially tight as this problem can be easily approximated within factor k. Our construction makes use of the biased Long-Code and is analyzed using combinatorial properties of s-wise t-intersecting families of subsets.

Given a database of n points in (0,1)d, the partial match problem is: In response to a query x in (0, 1, *)d, find a database point y such that for every i whenever xi ≠ *, we have xi = yi. In this paper we show randomized lower bounds in the cell-probe model for this well-studied problem[18, 11, 19, 16, 4, 6 ].Our lower bounds follow from a two-party asymmetric randomized communication complexity near-optimal lower bound for this problem, where we show that either Alice has to send Ω(d log n) bits or Bob has to send Ω(n1 - o(1)) bits. When applied to the cell-probe model, it means that if the number of cells is restricted to be poly(n, d) where each cell is of size poly(log n, d), then Ω(d/log2 n) probes are needed. This is an exponential improvement over the previously known lower bounds for this problem[16, 4].

A 2-prover game is called unique if the answer of one prover uniquely determines the answer of the second prover and vice versa (we implicitly assume games to be one round games). The value of a 2-prover game is the maximum acceptance probability of the verifier over all the prover strategies. We make a conjecture regarding the power of unique 2-prover games, which we call the Unique Games Conjecture.

We consider the problem of coloring a 3-colorable 3-uniform hypergraph. In the minimization version of this problem, given a 3-colorable 3-uniform hypergraph, one seeks an algorithm to color the hypergraph with as few colors as possible. We show that it is NP-hard to color a 3-colorable 3-uniform hypergraph with constantly many colors. In fact, we show a stronger result that it is NP-hard to distinguish whether a 3-uniform hypergraph with n vertices is 3-colorable or it contains no independent set of size /spl delta/n for an arbitrarily small constant /spl delta/ > 0. In the maximization version of the problem, given a 3-uniform hypergraph, the goal is to color the vertices with 3 colors so as to maximize the number of non-monochromatic edges. We show that it is NP-hard to distinguish whether a 3-uniform hypergraph is 3-colorable or any coloring of the vertices with 3 colors has at most 8/9 + /spl epsi/ fraction of the edges nonmonochromatic where /spl epsi/ > 0 is an arbitrarily small constant. This result is tight since assigning a random color independently to every vertex makes 8/9 fraction of the edges non-monochromatic. These results are obtained via a new construction of a probabilistically checkable proof system (PCP) for NP. We develop a new construction of the PCP Outer Verifier. An important feature of this construction is smoothening of the projection maps. Dinur, Regev and Smyth (2002) independently showed that it is NP-hard to color a 2-colorable 3-uniform hypergraph with constantly many colors. In the "good case", the hypergraph they construct is 2-colorable and hence their result is stronger. In the "bad case" however, the hypergraph we construct has a stronger property, namely, it does not even contain an independent set of size /spl delta/n.

Motivated by applications in vision and pattern detection, we introduce the following problem. We are given pairs of datapoints (x 1 , y 1 ), (x 2 , y 2 ), bound d, and a threshold # > 0. We desire "every" degree d polynomial h satisfying #, y i for at least # fraction of i's.

(MATH) Guruswami et al [6] show the hardness of coloring 2-colorable 4-uniform hypergraphs on n vertices with ω(log log n \over log log log n}) colors assuming NP $\not\subseteq$ DTIME(nO log log n)). We obtain a stronger hardness result for approximate coloring of p-colorable 4-uniform hypergraphs for any fixed integer p ≥ 7. We prove that there exists an absolute constant c < 0 such that for every fixed integer p ≥ 7, it is hard to color a p-colorable 4-uniform hypergraph with (log n)cp colors assuming NP $\not \subseteq$ DTIME(2(log n)O(1)).This work builds on the idea of "covering complexity" of probabilistically checkable proof systems (PCPs) developed in [6] and we introduce some new techniques as well. Firstly, we define a new code which we call the Split Code. This is a variation of the Long Code, but much shorter in length and it reduces the proof size significantly. Split Codes enable us to exploit the special structure of the "outer PCP verifier" constructed via Raz's Parallel Repetition Theorem [18]. Secondly, we make a novel use of the Split Codes over the domain GF(p) for a prime p. Working over non-boolean domain in fact makes our proof technically simpler than the proof of Guruswami at al [6].

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

For every integer k>1, we present a PCP characterization of NP where the verifier uses logarithmic randomness, queries 4k+k/sup 2/ bits in the proof, accepts a correct proof with probability 1 (i.e. it is has perfect completeness) and accepts any supposed proof of a false statement with a certain maximum probability. In particular, the verifier achieves optimal amortized query complexity of 1+/spl delta/ for arbitrarily small constant /spl delta/>0. Such a characterization was already proved by A. Samorodnitsky and L. Trevisan (2000), but their verifier loses perfect completeness and their proof makes an essential use of this feature. By using an adaptive verifier, we can decrease the number of query bits to 2k+k/sup 2/, the same number obtained by Samorodnitsky and Trevisan. Finally, we extend some of the results to larger domains.

The author presents improved inapproximability results for three problems: the problem of finding the maximum clique size in a graph, the problem of finding the chromatic number of a graph, and the problem of coloring a graph with a small chromatic number with a small number of colors. J. Hastad's (1996) result shows that the maximum clique size in a graph with n vertices is inapproximable in polynomial time within a factor n/sup 1-/spl epsi// or arbitrarily small constant /spl epsi/>0 unless NP=ZPP. We aim at getting the best subconstant value of /spl epsi/ in Hastad's result. We prove that clique size is inapproximable within a factor n/2((log n))/sup 1-y/ corresponding to /spl epsi/=1/(log n)/sup /spl gamma// for some constant /spl gamma/>0 unless NP/spl sube/ZPTIME(2((log n))/sup O(1)/). This improves the previous best inapproximability factor of n/2/sup O(log n//spl radic/log log n)/ (corresponding to /spl epsi/=O(1//spl radic/log log n)) due to L. Engebretsen and J. Holmerin (2000). A similar result is obtained for the problem of approximating chromatic number of a graph. We also present a new hardness result for approximate graph coloring. We show that for all sufficiently large constants k, it is NP-hard to color a k-colorable graph with k/sup 1/25 (log k)/ colors. This improves a result of M. Furer (1995) that for arbitrarily small constant /spl epsi/>0, for sufficiently large constants k, it is hard to color a k-colorable graph with k/sup 3/2-/spl epsi// colors.

We prove new results on evasiveness of monotone graph properties by extending the techniques of Kahn, Saks, and Sturtevant [Combinatorica, 4 (1984), pp. 297--306]. For the property of containing a subgraph isomorphic to a fixed graph, and a fairly large class of related n-vertex graph properties, we show evasiveness for an arithmetic progression of values of n. This implies a $\frac12n^2 - O(n)$ lower bound on the decision tree complexity of these properties. We prove that properties that are preserved under taking graph minors are evasive for all sufficiently large n. This greatly generalizes a theorem due to Best, van Emde Boas, and Lenstra [A Sharpened Version of the Aanderaa--Rosenberg Conjecture, Report ZW 30/74, Mathematisch Centrum, Amsterdam, The Netherlands, 1974] which states that planarity is evasive. We prove a similar result for bipartite subgraph containment.