All reports by Author Subhash Khot:

__
TR20-130
| 30th August 2020
__

Amey Bhangale, Subhash Khot#### Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups

__
TR20-009
| 6th February 2020
__

Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra#### Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality

__
TR19-148
| 1st November 2019
__

Amey Bhangale, Subhash Khot#### Simultaneous Max-Cut is harder to approximate than Max-Cut

Revisions: 1

__
TR19-141
| 22nd October 2019
__

Mark Braverman, Subhash Khot, Dor Minzer#### On Rich $2$-to-$1$ Games

__
TR19-093
| 15th July 2019
__

Prahladh Harsha, Subhash Khot, Euiwoong Lee, Devanathan Thiruvenkatachari#### Improved 3LIN Hardness via Linear Label Cover

__
TR19-004
| 11th January 2019
__

Amey Bhangale, Subhash Khot#### UG-hardness to NP-hardness by Losing Half

Revisions: 1

__
TR18-078
| 23rd April 2018
__

Subhash Khot, Dor Minzer, Dana Moshkovitz, Muli Safra#### Small Set Expansion in The Johnson Graph

__
TR18-006
| 10th January 2018
__

Subhash Khot, Dor Minzer, Muli Safra#### Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion

Revisions: 2

__
TR17-094
| 25th May 2017
__

Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra#### On Non-Optimally Expanding Sets in Grassmann Graphs

__
TR17-030
| 15th February 2017
__

Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari#### An Improved Dictatorship Test with Perfect Completeness

__
TR16-198
| 14th December 2016
__

Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra#### Towards a Proof of the 2-to-1 Games Conjecture?

__
TR16-126
| 8th August 2016
__

Subhash Khot, Igor Shinkar#### An $\widetilde{O}(n)$ Queries Adaptive Tester for Unateness

__
TR16-124
| 12th August 2016
__

Subhash Khot#### On Independent Sets, $2$-to-$2$ Games and Grassmann Graphs

Revisions: 1
,
Comments: 1

__
TR16-116
| 26th July 2016
__

Subhash Khot, Rishi Saket#### Approximating CSPs using LP Relaxation

__
TR15-013
| 28th January 2015
__

Subhash Khot, Igor Shinkar#### On Hardness of Approximating the Parameterized Clique Problem

__
TR15-011
| 22nd January 2015
__

Subhash Khot, Dor Minzer, Muli Safra#### On Monotonicity Testing and Boolean Isoperimetric type Theorems

__
TR14-142
| 1st November 2014
__

Subhash Khot, Dana Moshkovitz#### Candidate Lasserre Integrality Gap For Unique Games

__
TR14-051
| 12th April 2014
__

Subhash Khot, Rishi Saket#### Hardness of Coloring $2$-Colorable $12$-Uniform Hypergraphs with $2^{(\log n)^{\Omega(1)}}$ Colors

__
TR13-146
| 20th October 2013
__

Subhash Khot, Madhur Tulsiani, Pratik Worah#### A Characterization of Approximation Resistance

Revisions: 1

__
TR13-075
| 23rd May 2013
__

Subhash Khot, Madhur Tulsiani, Pratik Worah#### A Characterization of Strong Approximation Resistance

__
TR12-151
| 6th November 2012
__

Subhash Khot, Madhur Tulsiani, Pratik Worah#### The Complexity of Somewhat Approximation Resistant Predicates

Revisions: 1

__
TR12-109
| 31st August 2012
__

Subhash Khot, Muli Safra, Madhur Tulsiani#### Towards An Optimal Query Efficient PCP?

__
TR11-119
| 4th September 2011
__

Subhash Khot, Preyas Popat, Nisheeth Vishnoi#### $2^{\log^{1-\epsilon} n}$ Hardness for Closest Vector Problem with Preprocessing

__
TR10-112
| 15th July 2010
__

Subhash Khot, Dana Moshkovitz#### NP-Hardness of Approximately Solving Linear Equations Over Reals

__
TR10-053
| 28th March 2010
__

Dana Moshkovitz, Subhash Khot#### Hardness of Approximately Solving Linear Equations Over Reals

Comments: 1

__
TR07-073
| 3rd August 2007
__

Parikshit Gopalan, Subhash Khot, Rishi Saket#### Hardness of Reconstructing Multivariate Polynomials over Finite Fields

__
TR06-059
| 3rd May 2006
__

Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami#### New Results for Learning Noisy Parities and Halfspaces

__
TR05-101
| 20th September 2005
__

Guy Kindler, Ryan O'Donnell, Subhash Khot, Elchanan Mossel#### Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?

__
TR05-064
| 26th June 2005
__

Howard Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani#### On earthmover distance, metric labeling, and 0-extension

__
TR02-027
| 30th April 2002
__

Irit Dinur, Venkatesan Guruswami, Subhash Khot#### Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-\epsilon)

Amey Bhangale, Subhash Khot

A seminal result of H\r{a}stad [J. ACM, 48(4):798–859, 2001] shows that it is NP-hard to find an assignment that satisfies $\frac{1}{|G|}+\varepsilon$ fraction of the constraints of a given $k$-LIN instance over an abelian group, even if there is an assignment that satisfies $(1-\varepsilon)$ fraction of the constraints, for any constant ... more >>>

Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra

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

Amey Bhangale, Subhash Khot

A systematic study of simultaneous optimization of constraint satisfaction problems was initiated in [BKS15]. The simplest such problem is the simultaneous Max-Cut. [BKKST18] gave a $.878$-minimum approximation algorithm for simultaneous Max-Cut which is {\em almost optimal} assuming the Unique Games Conjecture (UGC). For a single instance Max-Cut, [GW95] gave an ... more >>>

Mark Braverman, Subhash Khot, Dor Minzer

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, we hope to understand ... more >>>

Prahladh Harsha, Subhash Khot, Euiwoong Lee, Devanathan Thiruvenkatachari

We prove that for every constant $c$ and $\epsilon = (\log n)^{-c}$, there is no polynomial time algorithm that when given an instance of 3LIN with $n$ variables where an $(1 - \epsilon)$-fraction of the clauses are satisfiable, finds an assignment that satisfies at least $(\frac{1}{2} + \epsilon)$-fraction of clauses ... more >>>

Amey Bhangale, Subhash Khot

The $2$-to-$2$ Games Theorem of [KMS-1, DKKMS-1, DKKMS-2, KMS-2] implies that it is NP-hard to distinguish between Unique Games instances with assignment satisfying at least $(\frac{1}{2}-\varepsilon)$ fraction of the constraints $vs.$ no assignment satisfying more than $\varepsilon$ fraction of the constraints, for every constant $\varepsilon>0$. We show that the reduction ... more >>>

Subhash Khot, Dor Minzer, Dana Moshkovitz, Muli Safra

This paper studies expansion properties of the (generalized) Johnson Graph. For natural numbers

t < l < k, the nodes of the graph are sets of size l in a universe of size k. Two sets are connected if

their intersection is of size t. The Johnson graph arises often ...
more >>>

Subhash Khot, Dor Minzer, Muli Safra

We prove that pseudorandom sets in Grassmann graph have near-perfect expansion as hypothesized in [DKKMS-2]. This completes

the proof of the $2$-to-$2$ Games Conjecture (albeit with imperfect completeness) as proposed in [KMS, DKKMS-1], along with a

contribution from [BKT].

The Grassmann graph $Gr_{global}$ contains induced subgraphs $Gr_{local}$ that are themselves ... more >>>

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

The paper investigates expansion properties of the Grassmann graph,

motivated by recent results of [KMS, DKKMS] concerning hardness

of the Vertex-Cover and of the $2$-to-$1$ Games problems. Proving the

hypotheses put forward by these papers seems to first require a better

understanding of these expansion properties.

We consider the edge ... more >>>

Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari

A Boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$ is called a dictator if it depends on exactly one variable i.e $f(x_1, x_2, \ldots, 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.

... more >>>Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra

We propose a combinatorial hypothesis regarding a subspace vs. subspace agreement test, and prove that if correct it leads to a proof of the 2-to-1 Games Conjecture, albeit with imperfect completeness.

Subhash Khot, Igor Shinkar

We present an adaptive tester for the unateness property of Boolean functions. Given a function $f:\{0,1\}^n \to \{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 any function that is $\epsilon$-far from being unate.

more >>>

Subhash Khot

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

Subhash Khot, Rishi Saket

This paper studies how well the standard LP relaxation approximates a $k$-ary constraint satisfaction problem (CSP) on label set $[L]$. We show that, assuming the Unique Games Conjecture, it achieves an approximation within $O(k^3\cdot \log L)$ of the optimal approximation factor. In particular we prove the following hardness result: let ... more >>>

Subhash Khot, Igor Shinkar

In the $Gap-clique(k, \frac{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 $\frac{k}{2}$. It is an open question in the study of fixed parameterized tractability whether the $Gap-clique(k, \frac{k}{2})$ problem ... more >>>

Subhash Khot, Dor Minzer, Muli Safra

We show a directed and robust analogue of a boolean isoperimetric type theorem of Talagrand. As an application, we

give a monotonicity testing algorithm that makes $\tilde{O}(\sqrt{n}/\epsilon^2)$ non-adaptive queries to a function

$f:\{0,1\}^n \mapsto \{0,1\}$, always accepts a monotone function and rejects a function that is $\epsilon$-far from

being monotone ...
more >>>

Subhash Khot, Dana Moshkovitz

We propose a candidate Lasserre integrality gap construction for the Unique Games problem.

Our construction is based on a suggestion in [KM STOC'11] wherein the authors study the complexity of approximately solving a system of linear equations over reals and suggest it as an avenue towards a (positive) resolution ...
more >>>

Subhash Khot, Rishi Saket

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 et al. [GHHSV14] 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 ... more >>>

Subhash Khot, Madhur Tulsiani, Pratik Worah

A predicate $f:\{-1,1\}^k \mapsto \{0,1\}$ with $\rho(f) = \frac{|f^{-1}(1)|}{2^k}$ is called {\it approximation resistant} if given a near-satisfiable instance of CSP$(f)$, it is computationally hard to find an assignment that satisfies at least $\rho(f)+\Omega(1)$ fraction of the constraints.

We present a complete characterization of approximation resistant predicates under the ... more >>>

Subhash Khot, Madhur Tulsiani, Pratik Worah

For a predicate $f:\{-1,1\}^k \mapsto \{0,1\}$ with $\rho(f) = \frac{|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 $[\rho(f)-\Omega(1), \rho(f)+\Omega(1)]$.

We present a characterization of ... more >>>

Subhash Khot, Madhur Tulsiani, Pratik Worah

A boolean predicate $f:\{0,1\}^k\to\{0,1\}$ is said to be {\em somewhat approximation resistant} if for some constant $\tau > \frac{|f^{-1}(1)|}{2^k}$, given a $\tau$-satisfiable instance of the MAX-$k$-CSP$(f)$ problem, it is NP-hard to find an assignment that {\it strictly beats} the naive algorithm that outputs a uniformly random assignment. Let $\tau(f)$ denote ... more >>>

Subhash Khot, Muli Safra, Madhur Tulsiani

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

Subhash Khot, Preyas Popat, Nisheeth Vishnoi

We prove that for an arbitrarily small constant $\eps>0,$ assuming NP$\not \subseteq$DTIME$(2^{{\log^{O(1/\epsilon)} 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-\epsilon}n}.$ This improves upon the previous hardness factor of $(\log n)^\delta$ for some $\delta ... more >>>

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.

Since the all-zero assignment always satisfies all the equations exactly, we restrict the assignments to be ``non-trivial". Here is

an informal statement of our ...
more >>>

Dana Moshkovitz, Subhash Khot

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 ``non-trivial". Here is

an informal statement of our ...
more >>>

Parikshit Gopalan, Subhash Khot, Rishi Saket

We study the polynomial reconstruction problem for low-degree

multivariate polynomials over finite fields. In the GF[2] version of this problem, we are given a set of points on the hypercube and target values $f(x)$ for each of these points, with the promise that there is a polynomial over GF[2] of ...
more >>>

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

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 classification noise,also called the noisy parity problem is a famous open problem in computational learning. We reduce a number of basic problems regarding ... more >>>

Guy Kindler, Ryan O'Donnell, Subhash Khot, 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 + \eps$, for all $\eps > 0$; here $\GW \approx .878567$ denotes the approximation ratio achieved by the Goemans-Williamson algorithm~\cite{GW95}. This implies that if the Unique ... more >>>

Howard Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani

We study the classification problem {\sc Metric Labeling} and its special case {\sc 0-Extension} in the context of earthmover metrics. Researchers recently proposed using earthmover metrics to get a polynomial time-solvable relaxation of {\sc Metric Labeling}; until now, however, no one knew if the integrality ratio was constant or not, ... more >>>

Irit Dinur, Venkatesan Guruswami, Subhash Khot

Given a $k$-uniform hypergraph, the E$k$-Vertex-Cover problem is

to find a minimum subset of vertices that ``hits'' every edge. We

show that for every integer $k \geq 5$, E$k$-Vertex-Cover is

NP-hard to approximate within a factor of $(k-3-\epsilon)$, for

an arbitrarily small constant $\epsilon > 0$.

This almost matches the ... more >>>