Linear equations modulo 2 and the L1 diameter of convex bodies (2009)
We design a randomized polynomial time algorithm which, given a 3-tensor of real numbers A = {ai jk} n
Approximate kernel clustering (2009)
In the kernel clustering problem we are given a large n × n positive semi-de nite matrix A = (aij) with ∑n i,j=1 aij = 0 and a small k ×k positive semi-de nite matrix B = (bij). The goal is to nd...
We design a randomized polynomial time algorithm which, given a 3-tensor of real numbers A = {aijk} n i,j,k=1 such that for all i, j, k ∈ {1,..., n} we have aijk = aikj =
Minimizing Wide Range Regret with Time Selection Functions (2009)
Subhash Khot, Ashok Kumar Ponnuswami
We consider the problem of minimizing regret with respect to a given set S of pairs of time selection functions and modifications rules. We give an online algorithm that has O ( √ T log |S|) regret...
Sharp kernel clustering algorithms and their associated Grothendieck inequalities (2009)
In the kernel clustering problem we are given a (large) $n\times n$ symmetric positive semidefinite matrix $A=(a_{ij})$ with $\sum_{i=1}^n\sum_{j=1}^n a_{ij}=0$ and a (small) $k\times k$ symmetric...
On Earthmover Distance, Metric Labeling, and 0-Extension (2008)
Howard Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani
We study the classification problem Metric Labeling and its special case 0-Extension in the context of earthmover metrics. Researchers recently proposed using earthmover metrics to get a polynomial...
1. A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover (2008)
Advisor Luca Trevisan, Sanjeev Arora, Subhash Khot, Ra Kolla, David Steurer, Nisheeth Vishnoi
We prove that the integrality gap for Vertex Cover remains at least 7/6 − ɛ after Ωɛ(n) rounds of LS+ method, which generates tighter semidefinite relaxations at each round. Our results apply...
Vitaly Feldman, Subhash Khot, Parikshit Gopalan
We study the learnability of several fundamental concept classes in the agnostic learning framework of Haussler [Hau92] and Kearns et al. [KSS94]. We show that under the uniform distribution,...
Vertex Cover Might be Hard to Approximate to (2008)
Abstract Based on a conjecture regarding the power of unique 2-prover-1-round games presented in[Khot02], we show that vertex cover is hard to approximate within any constant factor better than 2. We...
Vitaly Feldman, Subhash Khot, Parikshit Gopalan
We study the learnability of several fundamental concept classes in the agnostic learning framework of Haussler [Hau92] and Kearns et al. [KSS94]. We show that under the uniform distribution,...
Approximation Algorithms for the Max-Min Allocation problem (2008)
Subhash Khot, Ashok Kumar Ponnuswami
Abstract. The Max-Min allocation problem is to distribute indivisible goods to people so as to maximize the minimum utility of the people. We show a (2k − 1)-approximation algorithm for Max-Min...
Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique (2008)
Abstract Assuming that NP 6 ` "ffl?0 BPTIME(2nffl), we show that Graph Min-Bisection, Dense kSubgraph and Bipartite Clique have no Polynomial Time Approximation Scheme (PTAS). We give a...
Approximate kernel clustering (2008)
In the kernel clustering problem we are given a large $n\times n$ positive semi-definite matrix $A=(a_{ij})$ with $\sum_{i,j=1}^na_{ij}=0$ and a small $k\times k$ positive semi-definite matrix...
Extension and Metric Labeling. 0-Extension is closely (2008)
Howard Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani
We study the fundamental classification problems 0-
Hardness of Embedding Metric Spaces of Equal Size (2008)
Abstract. We study the problem embedding an n-point metric space into another n-point metric space while minimizing distortion. We show that there is no polynomial time algorithm to approximate the...
Vitaly Feldman, Subhash Khot, Parikshit Gopalan
We address well-studied problems concerning the learnability of parities and halfspaces in the presence of classification noise. Learning of parities under the uniform distribution with random...
Given a graph with maximum cut of (fractional) size c, the Goemans-Williamson [GW95] semidefinite programming (SDP) algorithm is guaranteed to find a cut of size.878 · c. However this guarantee...
Various new nonembeddability results (mainly into L1) are proved via Fourier analysis. In particular, it is shown that the Edit Distance on {0, 1} d has L1 distortion Ω ( � log d / log log d). We...
Parikshit Gopalan, Rishi Saket, Subhash Khot
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 ∈ {0, 1} n and target values f(x) ∈ {0, 1} for...
Parikshit Gopalan, Rishi Saket, Subhash Khot
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 ∈ {0, 1} n and target values f(x) ∈ {0, 1} for...
Parameterized complexity of finding subgraphs with hereditary properties (2008)
Abstract. We consider the parameterized complexity of the following problem under the framework introduced by Downey and Fellows[4]: Given a graph G, an integer parameter k and a non-trivial...
T. S. Jayram, Subhash Khot, Yuval Rabani
Given a database of n points in f0; 1g d, the partial match problem is: In response to a query x in f0; 1; g d, find a database point y such that for every i whenever x i 6 =, we have x i = y i. In...
Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev
Given a k-uniform hyper-graph, the Ek-Vertex-Cover problem is to nd the minimum-size subset of vertices that `hits ' every hyper-edge. We present a new multilayered PCP construction that extends...
New results for learning noisy parities and halfspaces (2006)
Vitaly Feldman, Subhash Khot, Parikshit Gopalan
We address well-studied problems concerning the learnability of parities and halfspaces in the presence of classification noise. Learning of parities under the uniform distribution with random...
New results for learning noisy parities and halfspaces (2006)
Vitaly Feldman, Subhash Khot, Parikshit Gopalan
We address well-studied problems concerning the learnability of parities and halfspaces in the presence of classification noise. Learning of parities under the uniform distribution with random...
Vitaly Feldman, Subhash Khot, Parikshit Gopalan
We address well-studied problems concerning the learnability of parities and halfspaces in the presence of classification noise. Learning of parities under the uniform distribution with random...
Nonembeddability theorems via Fourier analysis (2005)
Various new nonembeddability results (mainly into $L_1$) are proved via Fourier analysis. In particular, it is shown that the Edit Distance on $\{0,1\}^d$ has $L_1$ distortion $(\log...
Inapproximability results for combinatorial auctions with submodular utility functions (2005)
Subhash Khot, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta
We consider the following allocation problem arising in the setting of combinatorial auctions: a set of goods is to be allocated to a set of players so as to maximize the sum of the utilities of the...
Subhash Khot, Guy Kindler, Elchanan Mossel
In this paper we show a reduction from the Unique Games problem to the problem of approximating MAX-CUT to within a factor of α GW + ɛ, for all ɛ> 0; here α GW ≈.878567 denotes the...
Combinatorial Theorems about Embedding Trees on the Real Line ∗ (2005)
Amit Chakrabarti, Subhash Khot
We consider the combinatorial problem of embedding a tree metric into the real line with low distortion. For two special families of trees — the family of complete binary trees and the family of...
Subhash Khot, Guy Kindler, Elchanan Mossel
In this paper we show a reduction from the Unique Games problem to the problem of approximating MAX-CUT to within a factor of αGW + ɛ, for all ɛ> 0; here αGW ≈.878567 denotes the...
Inapproximability results for combinatorial auctions with submodular utility functions (2005)
Subhash Khot, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta
We consider the following allocation problem arising in the setting of combinatorial auctions: a set of goods is to be allocated to a set of players so as to maximize the sum of the utilities of the...
Optimal inapproximability results for MAX-CUT and other 2-variable CSPs (2004)
Subhash Khot, Guy Kindler, Elchanan Mossel
In this paper we give evidence suggesting that MAX-CUT is NP-hard to approximate to within a factor of αGW+ɛ, for all ɛ> 0, where αGW denotes the approximation ratio achieved by the...
Optimal inapproximability results for MAX-CUT and other 2-variable CSPs (2004)
Subhash Khot, Elchanan Mossel, Guy Kindler
In this paper we show a reduction from the Unique Games problem to the problem of approximating MAX-CUT to within a factor of αGW + ɛ, for all ɛ> 0; here αGW ≈.878567 denotes the...
Preliminary version Abstract (2004)
Subhash Khot, Elchanan Mossel, Guy Kindler
In this paper we give evidence that it is NP-hard to approximate MAX-CUT to within a factor of α GW+ɛ, for all ɛ> 0. Here α GW denotes the approximation ratio achieved by the...
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover (2003)
Dinur, Irit, Guruswami, Venkatesan, Khot, Subhash, Regev, Oded
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...
Near-optimal lower bounds on the multi-party communication complexity of set disjointness (2003)
Amit Chakrabarti, Subhash Khot, Xiaodong Sun
We study the communication complexity of the set disjointness problem in the general multi-party model. For t players, each holding a subset of a universe of size n, we establish a near-optimal lower...
A new multilayered PCP and the hardness of hypergraph vertex cover (2003)
Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev
Abstract Given a k-uniform hypergraph, the Ek-Vertex-Cover problem is to find the smallest subsetof vertices that intersects every hyperedge. We present a new multilayered PCP construction that...
Vertex cover might be hard to approximate to within 2 − ε (2003)
We show that vertex cover is hard to approximate within any constant factor better than 2 where the hardness is based on a conjecture regarding the power of unique 2-prover-1-round games presented in...
Hardness of Lattice Problems in ℓp Norm (2003)
Subhash Khot, Nisheeth K. Vishnoi
We show that for any integer p ≥ 46, the Shortest Vector Problem in ℓp norm is hard to approximate within factor (4/3) 1−45.7/p. We also show a hardness factor of (3/2) 1−111.7/p for p ≥...
Cell-probe lower bounds for the partial match problem (2003)
T. S. Jayram, Subhash Khot, Ravi Kumar, 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 xi � = ∗, we have xi =...
jh(xi) \Gamma yij ^ ffi for at least ae fraction of the indices i (1) If ffi = 0, this is just the list decoding problem that has been popular in complexity theory and for which Sudan gave a poly(m;...
Hardness results for coloring 3-colorable 3-uniform hypergraphs (2002)
Abstract In this paper, we consider the problem of coloring a 3-colorable 3-uniform hypergraph. In the minimization ver-sion of this problem, given a 3-colorable 3-uniform hyper-graph, one seeks an...
Fitting algebraic curves to noisy data (2002)
We introduce the following problem which is motivated by applications in vision and pattern detection: We are given pairs of datapoints (x 1, y 1), (x 2, y 2),..., (xm, ym)
On the power of unique 2-prover 1-round games (2002)
ABSTRACT 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...
Fitting algebraic curves to noisy data (2002)
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),..., (xm, ym), a noise parameter #> 0, a...
Evasiveness of subgraph containment and related properties (2002)
Amit Chakrabarti, Subhash Khot, Yaoyun Shi
Abstract. We prove new results on evasiveness of monotone graph properties by extending the techniques of Kahn, Saks and Sturtevant [4]. For the property of containing a subgraph isomorphic to a xed...
Subhash Khot, Ashok Kumar Ponnuswami
Abstract. We prove an improved hardness of approximation result for two problems, namely, the problem of finding the size of the largest clique in a graph and the problem of finding the chromatic...
Query efficient PCPs with perfect completeness (2001)
For every integer k> 0, we present a PCP characterization of NP where the verifier uses logarithmic randomness, queries 4k + k 2 bits in the proof, accepts a correct proof with probability 1 (i.e....
Subhash Khot, Ashok Kumar Ponnuswami
Abstract. We prove an improved hardness of approximation result for two problems, namely, the problem of finding the size of the largest clique in a graph and the problem of finding the chromatic...
Query efficient PCPs with perfect completeness (2001)
Subhash Khot, J. H ˚astad, S. Khot
Abstract: For every integer k> 0, and an arbitrarily small constant ε> 0, we present a PCP characterization of NP where the verifier uses logarithmic randomness, non-adaptively queries 4k + k2...