Subhash Khot

SODA Conference 2025 Conference Paper

Maximum Span Hypothesis: A Potentially Weaker Assumption than Gap-ETH for Parameterized Complexity

• Karthik C. S. 0001
• Subhash Khot

STOC Conference 2025 Conference Paper

On Approximability of Satisfiable k-CSPs: V

• Amey Bhangale
• Subhash Khot
• Dor Minzer

FOCS Conference 2025 Conference Paper

On Inverse Theorems and Combinatorial Lines

• Amey Bhangale
• Subhash Khot
• Yang P. Liu
• Dor Minzer

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 f 1, …, f k that 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} n with density at least Ω((loglogloglogn) −c ) must contain a combinatorial line, i. e. , x, y, z ∈ {0, 1, 2} n, not all equal, such that x i = y i = z i or (x i, y i, z i ) = (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.

STOC Conference 2025 Conference Paper

Parallel Repetition for 3-Player XOR Games

• Amey Bhangale
• Mark Braverman
• Subhash Khot
• Yang P. Liu
• Dor Minzer

STOC Conference 2024 Conference Paper

On Approximability of Satisfiable k-CSPs: IV

• Amey Bhangale
• Subhash Khot
• Dor Minzer

STOC Conference 2023 Conference Paper

On Approximability of Satisfiable k-CSPs: II

• Amey Bhangale
• Subhash Khot
• Dor Minzer

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.

STOC Conference 2023 Conference Paper

On Approximability of Satisfiable k-CSPs: III

• Amey Bhangale
• Subhash Khot
• Dor Minzer

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.

FOCS Conference 2023 Conference Paper

Parallel Repetition for the GHZ Game: Exponential Decay

• Mark Braverman
• Subhash Khot
• Dor Minzer

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.

STOC Conference 2022 Conference Paper

On approximability of satisfiable k -CSPs: I

• Amey Bhangale
• Subhash Khot
• Dor Minzer

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.

FOCS Conference 2021 Conference Paper

An Invariance Principle for the Multi-slice, with Applications

• Mark Braverman
• Subhash Khot
• Noam Lifshitz
• Dor Minzer

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.

STOC Conference 2021 Conference Paper

Optimal inapproximability of satisfiable k-LIN over non-abelian groups

• Amey Bhangale
• Subhash Khot

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.

SODA Conference 2019 Conference Paper

The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics

• Subhash Khot
• Assaf Naor

SODA Conference 2018 Conference Paper

Near-optimal approximation algorithm for simultaneous Max-Cut

• Amey Bhangale
• Subhash Khot
• Swastik Kopparty
• Sushant Sachdeva
• Devanathan Thiruvenkatachari

STOC Conference 2018 Conference Paper

On non-optimally expanding sets in Grassmann graphs

• Irit Dinur
• Subhash Khot
• Guy Kindler
• Dor Minzer
• Muli Safra

We study the structure of non-expanding sets in the Grassmann graph. We put forth a hypothesis stating that every small set whose expansion is smaller than 1−δ must be correlated with one of a specified list of sets which are isomorphic to smaller Grassmann graphs. We develop a framework of Fourier analysis for analyzing functions over the Grassmann graph, and prove that our hypothesis holds for all sets whose expansion is below 7/8. In the companion submitted paper [Dinur, Khot, Kindler, Minzer and Safra, STOC 2018], the authors show that a linearity agreement hypothesis implies an NP-hardness gap of 1/2− vs for unique games and other inapproximability results. In [Barak, Kothari and Steurer, ECCC TR18-077], the authors show that the hypothesis in this work implies the linearity agreement hypothesis of [Dinur, Khot, Kindler, Minzer and Safra, STOC 2018]. Combined with our main theorem here this proves a version of the linearity agreement hypothesis with certain specific parameters. Short of proving the entire hypothesis, this nevertheless suffices for getting new unconditional NP hardness gaps for label cover with 2-to-1 and unique constraints. Our Expansion Hypothesis has been subsequently proved in its full form [Khot, Minzer and Safra, ECCC TR18-006] thereby proving the agreement hypothesis of [Dinur, Khot, Kindler, Minzer and Safra, STOC 2018] and completing the proof of the 2-to-1 Games Conjecture (albeit with imperfect completeness).

FOCS Conference 2018 Conference Paper

Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion

• Subhash Khot
• Dor Minzer
• Muli Safra

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.

STOC Conference 2018 Conference Paper

Towards a proof of the 2-to-1 games conjecture?

• Irit Dinur
• Subhash Khot
• Guy Kindler
• Dor Minzer
• Muli Safra

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. Our work builds on earlier work by a subset of the authors [Khot, Minzer and Safra, STOC 2017] where a slightly different hypothesis was used to obtain hardness of approximating vertex cover to within factor of √2−ε. The most important implication of this work is (assuming the hypothesis) an NP-hardness gap of 1/2−ε vs. ε for unique games . In addition, we derive optimal NP-hardness for approximating the max-cut-gain problem, NP-hardness of coloring an almost 4-colorable graph with any constant number of colors, and the same √2−ε NP-hardness for approximate vertex cover that was already obtained based on a slightly different hypothesis. Recent progress towards proving our hypothesis [Barak, Kothari and Steurer, ECCC TR18-077], [Dinur, Khot, Kindler, Minzer and Safra, STOC 2018] directly implies some new unconditional NP-hardness results. These include new points of NP-hardness for unique games and for 2-to-1 and 2-to-2 games. More recently, the full version of our hypothesis was proven [Khot, Minzer and Safra, ECCC TR18-006].

STOC Conference 2017 Conference Paper

On independent sets, 2-to-2 games, and Grassmann graphs

• Subhash Khot
• Dor Minzer
• Muli Safra

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).

STOC Conference 2016 Conference Paper

Candidate hard unique game

• Subhash Khot
• Dana Moshkovitz

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.

FOCS Conference 2015 Conference Paper

On Monotonicity Testing and Boolean Isoperimetric Type Theorems

• Subhash Khot
• Dor Minzer
• Muli Safra

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.

STOC Conference 2014 Conference Paper

A characterization of strong approximation resistance

• Subhash Khot
• Madhur Tulsiani
• Pratik Worah

For a predicate f : {-1, 1} k ↦ {0, 1} with ρ ( f ) = | f -1 (1)|/2 k , 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)].

FOCS Conference 2014 Conference Paper

Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with exp(log^{Omega(1)} n) Colors

• Subhash Khot
• Rishi Saket

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.

SODA Conference 2014 Conference Paper

Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs

• Subhash Khot
• Rishi Saket

STOC Conference 2012 Conference Paper

2 log1-ε n hardness for the closest vector problem with preprocessing

• Subhash Khot
• Preyas Popat
• Nisheeth K. Vishnoi

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

FOCS Conference 2012 Conference Paper

Hardness of Finding Independent Sets in Almost q-Colorable Graphs

• Subhash Khot
• Rishi Saket

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

FOCS Conference 2011 Conference Paper

A Two Prover One Round Game with Strong Soundness

• Subhash Khot
• Muli Safra

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 q 6 answers 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).

STOC Conference 2011 Conference Paper

NP-hardness of approximately solving linear equations over reals

• Subhash Khot
• Dana Moshkovitz

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.

FOCS Conference 2010 Conference Paper

Hardness of Finding Independent Sets in Almost 3-Colorable Graphs

• Irit Dinur
• Subhash Khot
• Will Perkins 0001
• Muli Safra

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/q 2.

SODA Conference 2010 Conference Paper

Sharp Kernel Clustering Algorithms and Their Associated Grothendieck Inequalities

• Subhash Khot
• Assaf Naor

FOCS Conference 2009 Conference Paper

Optimal Long Code Test with One Free Bit

• Nikhil Bansal 0001
• Subhash Khot

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-¿.

FOCS Conference 2009 Conference Paper

SDP Integrality Gaps with Local ell_1-Embeddability

• Subhash Khot
• Rishi Saket

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 l 1. The local l 1 -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 α GW is 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 l 1 -embeddable, but embedding the whole metric into l 1 incurs distortion Ω((log log log n) 1/13 ).

FOCS Conference 2008 Conference Paper

Approximate Kernel Clustering

• Subhash Khot
• Assaf Naor

In the kernel clustering problem we are given a large ntimesn positive semi-definite matrix A=(a ij ) with Sigma i, j n =1 a ij =0 and a small ktimesk positivesemi-definite matrix B=b ij. The goal is to find a partition S 1, .. S k of {1, .. .n} which maximizes the quantity Sigma i, j=1 k (Sigma (i, j)isinS i timesS j ). 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.

FOCS Conference 2008 Conference Paper

Hardness of Minimizing and Learning DNF Expressions

• Subhash Khot
• Rishi Saket

We study the problem of finding the minimum size DNF formula for a function f: {0, 1} d rarr {0, 1} given its truth table. We show that unless NP sube DTIME(n poly(log n) ), there is no polynomial time algorithm that approximates this problem to within factor d 1-epsiv where 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.

STOC Conference 2008 Conference Paper

On hardness of learning intersection of two halfspaces

• Subhash Khot
• Rishi Saket

We show that unless NP = RP, it is hard to (even) weakly PAC-learn intersection of two halfspaces in R n 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 R n , or whether any function of l linear threshold functions can correctly classify at most 1/2+ε fraction of the points.

STOC Conference 2008 Conference Paper

Unique games on expanding constraint graphs are easy: extended abstract

• Sanjeev Arora
• Subhash Khot
• Alexandra Kolla
• David Steurer
• Madhur Tulsiani
• Nisheeth K. Vishnoi

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

FOCS Conference 2007 Conference Paper

Hardness of Reconstructing Multivariate Polynomials over Finite Fields

• Parikshit Gopalan
• Subhash Khot
• Rishi Saket

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} n and 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.

FOCS Conference 2007 Conference Paper

Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies

• Subhash Khot
• Assaf Naor

We design a randomized polynomial time algorithm which, given a 3-tensor of real numbers A={a ijk } ij, k=1 n such that for all i, j, kisin{1, .. ., n} we have a ijk =a ikj =a kji =a jik =a kij =a kji and a iik =a ijj =a iji =0, computes a number Alg(A) which satisfies with probability at least 1/2, Omega(radic(logn/n))ldrmax xisin{-1, 1} n Sigma i, j, k=1 n a ijk x i x j x k lesAlg(A)lesmax xisin{-1, 1} n Sigma i, j, k=1 n a ijk x i x j x k. 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 max xisin{-1, 1} n Sigma i, j, k=1 n a ijk x i x j x k within a factor of 2(logn) t-epsiv in time 2 (logn) O(1). Our algorithm is based on a reduction to the problem of computing the diameter of a convex body in 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(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.

STOC Conference 2006 Conference Paper

Integrality gaps for sparsest cut and minimum linear arrangement problems

• Nikhil R. Devanur
• Subhash Khot
• Rishi Saket
• Nisheeth K. Vishnoi

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).

FOCS Conference 2006 Conference Paper

New Results for Learning Noisy Parities and Halfspaces

• Vitaly Feldman
• Parikshit Gopalan
• Subhash Khot
• Ashok Kumar Ponnuswami

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 Qopf n with 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

STOC Conference 2006 Conference Paper

On earthmover distance, metric labeling, and 0-extension

• Howard J. Karloff
• Subhash Khot
• Aranyak Mehta
• Yuval Rabani

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 that the integrality ratio of the earthmover relaxation for METRIC LABELING is Ω(log n) (which is asymptotically tight), k being the number of labels, whereas the best previous lower bound on the integrality ratio was only constant; that the integrality ratio of the earthmover relaxation for O-EXTENSION is Ω(√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; that for no ε>0 is there a polynomial-time O((log n) 1/4-ε )-approximation algorithm for O-EXTENSION, n being the number of vertices, unless NP ⊆ DTIME(n poly(log n) ), whereas the strongest inapproximability result known before was only MAX SNP-hardness; and that there is a polynomial-time approximation algorithm for O-EXTENSION with performance ratio O(√diam(d)), where diam(d) is the ratio of the largest to smallest nonzero distances in the terminal metric.

FOCS Conference 2006 Conference Paper

SDP gaps and UGC-hardness for MAXCUTGAIN

• Subhash Khot
• Ryan O'Donnell

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 par infin rarr 1 norm of a matrix

FOCS Conference 2005 Conference Paper

Hardness of Approximating the Closest Vector Problem with Pre-Processing

• Michael Alekhnovich
• Subhash Khot
• Guy Kindler
• Nisheeth K. Vishnoi

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.

FOCS Conference 2005 Conference Paper

Nonembeddability theorems via Fourier analysis

• Subhash Khot
• Assaf Naor

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.

FOCS Conference 2005 Conference Paper

On the Unique Games Conjecture

• Subhash Khot

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.

FOCS Conference 2005 Conference Paper

The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into l 1

• Subhash Khot
• Nisheeth K. Vishnoi

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.

STOC Conference 2004 Conference Paper

A new PCP outer verifier with applications to homogeneous linear equations and max-bisection

• Jonas Holmerin
• Subhash Khot

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(2 n ε ).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.

FOCS Conference 2004 Conference Paper

Hardness of Approximating the Shortest Vector Problem in Lattices

• Subhash Khot

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//.

FOCS Conference 2004 Conference Paper

Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?

• Subhash Khot
• Guy Kindler
• Elchanan Mossel
• Ryan O'Donnell

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.

FOCS Conference 2004 Conference Paper

Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique

• Subhash Khot

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.

STOC Conference 2003 Conference Paper

A new multilayered PCP and the hardness of hypergraph vertex cover

• Irit Dinur
• Venkatesan Guruswami
• Subhash Khot
• Oded Regev 0001

Given a k -uniform hyper-graph, the E k -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 E k -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.

STOC Conference 2003 Conference Paper

Cell-probe lower bounds for the partial match problem

• T. S. Jayram
• Subhash Khot
• Ravi Kumar 0001
• Yuval Rabani

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 x i ≠ *, we have x i = y i . 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 Ω(n 1 - 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/log 2 n) probes are needed. This is an exponential improvement over the previously known lower bounds for this problem[16, 4].

FOCS Conference 2003 Conference Paper

Hardness of Approximating the Shortest Vector Problem in High L p Norms

• Subhash Khot

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).

STOC Conference 2002 Conference Paper

Fitting algebraic curves to noisy data

• Sanjeev Arora
• Subhash Khot

(MATH) 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)$, $\ldots,(x_m, y_m)$, a noise parameter $\delta > 0$, a degree bound $d$, and a threshold $\rho>0$. We desire "every" degree $d$ polynomial $h$ satisfying h(x_i) \in [y_i -\delta, y_i +\delta] & \qquad \nonumber for at least ρ fraction of i 's.(MATH) We assume by rescaling the data that each $x_i, y_i \in [-1, 1]$.(MATH) If $\delta =0$, this is just the list decoding problem that has been popular in complexity theory and for which Sudan gave a $\poly(d,1/\rho)$ time algorithm.We show a few basic results about the problem. We show that there is no polynomial time algorithm for this problem as defined; the number of solutions can be as large as exp( d 0.5 -ε ) even if the data is generated using a 50 - 50 mixture of two polynomials. We give a rigorous analysis of a brute force algorithm for the version of this problem where the data is generated from a mixture of polynomials. Finally, in surprising contrast to our "lower bound", we describe a polynomial-time algorithm for reconstructing mixtures of O (1) polynomials when the mixing weights are "nondegenerate.The tools used include classical theory of approximations.

STOC Conference 2002 Conference Paper

Hardness results for approximate hypergraph coloring

• Subhash Khot

(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( n O 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].

FOCS Conference 2002 Conference Paper

Hardness Results for Coloring 3 -Colorable 3 -Uniform Hypergraphs

• Subhash Khot

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.

STOC Conference 2002 Conference Paper

On the power of unique 2-prover 1-round games

• Subhash Khot

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 any $\frac{1}{2} 0$, it is NP-hard to distinguish between the instances of the problem 2-Linear-Equations mod 2 where either there exists an assignment that satisfies $1-\epsilon$ fraction of equations or no assignment can satisfy more than $1-\epsilon^t$ fraction of equations. As a corollary of the above result, it is NP-hard to approximate the Min-2CNF-deletion problem within any constant factor. For the constraint satisfaction problem where every constraint is the predicate Not-all-equal($a,b,c$), $ \ a, b, c \in GF(3) \ $, it is NP-hard to distinguish between the instances where either there exists an assignment that satisfies $1-\epsilon$ fraction of the constraints or no assignment satisfies more than $\frac{8}{9}+\epsilon$ fraction of the constraints for an arbitrarily small constant $\epsilon > 0$. We also get a hardness result for a slight variation of approximate coloring of 3-uniform hypergraphs. (MATH) We also show that a variation of the Unique Games Conjecture implies that for arbitrarily small constant $\delta > 0$ it is hard to find an independent set of size $\delta n$ in a graph that is guaranteed to have an independent set of size $\Omega(n)$.The main idea in all the above results is to use the 2-prover game given by the Unique Games Conjecture as an "outer verifier" and build new probabilistically checkable proof systems (PCPs) on top of it. The uniqueness property plays a crucial role in the analysis of these PCPs.(MATH) In light of such interesting consequences, we think it is an important open problem to prove (or disprove) the Unique Games Conjecture. We also present a semi-definite programming based algorithm for finding reasonable prover strategies for a unique 2-prover game. Given a unique 2-prover game with value $1-\zeta$ and answers from a domain of size $k$, this algorithm finds prover strategies that make the verifier accept with probability $1-O(k^2 \zeta^{1/5} \sqrt{\log (\frac{1}{\zeta})})$. This result shows that the domain size $k = k(\zeta, \delta)$ must be sufficiently large if the Unique Games Conjecture is true.

TCS Journal 2002 Journal Article

Parameterized complexity of finding subgraphs with hereditary properties

• Subhash Khot
• Venkatesh Raman

We consider the parameterized complexity of the following problem under the framework introduced by Downey and Fellows: Given a graph G, an integer parameter k and a nontrivial hereditary property Π, are there k vertices of G that induce a subgraph with property Π? This problem has been proved NP-hard by Lewis and Yannakakis. We show that if Π includes all trivial graphs but not all complete graphs or vice versa, then the problem is complete for the parameterized class W[1] and is fixed parameter tractable otherwise. Our proofs of both the tractability and hardness involve nontrivial use of the theory of Ramsey numbers.

FOCS Conference 2001 Conference Paper

Improved Inaproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring

• Subhash Khot

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.

FOCS Conference 2001 Conference Paper

Query Efficient PCPs with Perfect Completeness

• Johan Håstad
• Subhash Khot

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.