# Subhash Khot

Affiliations:
• New York University, NY, USA

According to our database1, Subhash Khot authored at least 108 papers between 2001 and 2022.

Collaborative distances:
• Dijkstra number2 of two.
• Erdős number3 of three.

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2022
On Approximability of Satisfiable <i>k</i>-CSPs: I.
Electron. Colloquium Comput. Complex., 2022

Almost Polynomial Factor Inapproximability for Parameterized k-Clique.
Proceedings of the 37th Computational Complexity Conference, 2022

2021
An Invariance Principle for the Multi-slice, with Applications.
Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020
Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality.
Electron. Colloquium Comput. Complex., 2020

Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups.
Electron. Colloquium Comput. Complex., 2020

2019
Improved 3LIN Hardness via Linear Label Cover.
Electron. Colloquium Comput. Complex., 2019

On Rich $2$-to-$1$ Games.
Electron. Colloquium Comput. Complex., 2019

Simultaneous Max-Cut is harder to approximate than Max-Cut.
Electron. Colloquium Comput. Complex., 2019

UG-hardness to NP-hardness by Losing Half.
Electron. Colloquium Comput. Complex., 2019

The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018
Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion.
Electron. Colloquium Comput. Complex., 2018

Small Set Expansion in The Johnson Graph.
Electron. Colloquium Comput. Complex., 2018

Near-optimal approximation algorithm for simultaneous Max-Cut.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017
Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with 2<sup>(log n)<sup>Ømega(1)</sup></sup> Colors.
SIAM J. Comput., 2017

On Non-Optimally Expanding Sets in Grassmann Graphs.
Electron. Colloquium Comput. Complex., 2017

An Improved Dictatorship Test with Perfect Completeness.
Electron. Colloquium Comput. Complex., 2017

2016
An Õ(n) Queries Adaptive Tester for Unateness.
Electron. Colloquium Comput. Complex., 2016

Approximating CSPs using LP Relaxation.
Electron. Colloquium Comput. Complex., 2016

On Independent Sets, 2-to-2 Games and Grassmann Graphs.
Electron. Colloquium Comput. Complex., 2016

Towards a Proof of the 2-to-1 Games Conjecture?
Electron. Colloquium Comput. Complex., 2016

An $\widetilde{O}(n)$ Queries Adaptive Tester for Unateness.
CoRR, 2016

Candidate hard unique game.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Hardness of Approximation.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Hardness of Bipartite Expansion.
Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2015
The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ<sub>1</sub>.
J. ACM, 2015

On Hardness of Approximating the Parameterized Clique Problem.
Electron. Colloquium Comput. Complex., 2015

On Monotonicity Testing and Boolean Isoperimetric type Theorems.
Electron. Colloquium Comput. Complex., 2015

2014
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem.
IEEE Trans. Inf. Theory, 2014

Almost Polynomial Factor Hardness for Closest Vector Problem with Preprocessing.
SIAM J. Comput., 2014

Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with 2<sup>log n<sup>Ω(1)</sup></sup> Colors.
Electron. Colloquium Comput. Complex., 2014

Candidate Lasserre Integrality Gap For Unique Games.
Electron. Colloquium Comput. Complex., 2014

Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with exp(log^{Omega(1)} n) Colors.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013
A Two-Prover One-Round Game with Strong Soundness.
Theory Comput., 2013

<i>NP</i>-Hardness of Approximately Solving Linear Equations over Reals.
SIAM J. Comput., 2013

Sharp kernel clustering algorithms and their associated Grothendieck inequalities.
Random Struct. Algorithms, 2013

A Characterization of Approximation Resistance.
Electron. Colloquium Comput. Complex., 2013

A Characterization of Strong Approximation Resistance.
Electron. Colloquium Comput. Complex., 2013

A characterization of approximation resistance for even k-partite CSPs.
Proceedings of the Innovations in Theoretical Computer Science, 2013

On Approximation Resistance of Predicates (Invited Talk).
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2013

2012
The Complexity of Somewhat Approximation Resistant Predicates.
Electron. Colloquium Comput. Complex., 2012

Towards An Optimal Query Efficient PCP?
Electron. Colloquium Comput. Complex., 2012

2<sup>log1-ε <i>n</i></sup> hardness for the closest vector problem with preprocessing.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Hardness of Finding Independent Sets in Almost q-Colorable Graphs.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs.
Theory Comput., 2011

Combinatorial theorems about embedding trees on the real line.
J. Graph Theory, 2011

On the hardness of learning intersections of two halfspaces.
J. Comput. Syst. Sci., 2011

2<sup>log<sup>1-έ</sup>n</sup> Hardness for Closest Vector Problem with Preprocessing.
Electron. Colloquium Comput. Complex., 2011

$2^{\log^{1-\eps} n}$ Hardness for Closest Vector Problem with Preprocessing
CoRR, 2011

Grothendieck-type inequalities in combinatorial optimization
CoRR, 2011

Hardness of Approximating the Closest Vector Problem with Pre-Processing.
Comput. Complex., 2011

2010
Inapproximability Results for Computational Problems on Lattices.
Proceedings of the LLL Algorithm - Survey and Applications, 2010

Hardness of Approximately Solving Linear Equations Over Reals.
Electron. Colloquium Comput. Complex., 2010

NP-Hardness of Approximately Solving Linear Equations Over Reals.
Electron. Colloquium Comput. Complex., 2010

Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)
CoRR, 2010

SDP Gaps for 2-to-1 and Other Label-Cover Variants.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Hardness of Finding Independent Sets in Almost 3-Colorable Graphs.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

On the Unique Games Conjecture (Invited Survey).
Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, 2010

Approximate Lasserre Integrality Gap for Unique Games.
Proceedings of the Approximation, 2010

2009
SDP Gaps and UGC-hardness for Max-Cut-Gain.
Theory Comput., 2009

On Agnostic Learning of Parities, Monomials, and Halfspaces.
SIAM J. Comput., 2009

SDP Integrality Gaps with Local ell_1-Embeddability.
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

Optimal Long Code Test with One Free Bit.
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008
Linear Equations Modulo 2 and the L<sub>1</sub> Diameter of Convex Bodies.
SIAM J. Comput., 2008

Vertex cover might be hard to approximate to within 2-epsilon.
J. Comput. Syst. Sci., 2008

Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions.
Algorithmica, 2008

On hardness of learning intersection of two halfspaces.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Unique games on expanding constraint graphs are easy: extended abstract.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Hardness of Minimizing and Learning DNF Expressions.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Approximate Kernel Clustering.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Minimizing Wide Range Regret with Time Selection Functions.
Proceedings of the 21st Annual Conference on Learning Theory, 2008

2007
Improved lower bounds on the randomized complexity of graph properties.
Random Struct. Algorithms, 2007

Hardness of Reconstructing Multivariate Polynomials over Finite Fields.
Electron. Colloquium Comput. Complex., 2007

Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

Hardness of Embedding Metric Spaces of Equal Size.
Proceedings of the Approximation, 2007

Approximation Algorithms for the Max-Min Allocation Problem.
Proceedings of the Approximation, 2007

2006
Ruling Out PTAS for Graph Min-Bisection, Dense k-Subgraph, and Bipartite Clique.
SIAM J. Comput., 2006

Hardness of approximating the Shortest Vector Problem in high <i>l<sub>p</sub></i> norms.
J. Comput. Syst. Sci., 2006

New Results for Learning Noisy Parities and Halfspaces.
Electron. Colloquium Comput. Complex., 2006

Integrality gaps for sparsest cut and minimum linear arrangement problems.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

SDP gaps and UGC-hardness for MAXCUTGAIN.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

A 3-Query Non-Adaptive PCP with Perfect Completeness.
Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

2005
Query Efficient PCPs with Perfect Completeness.
Theory Comput., 2005

Guest column: inapproximability results via Long Code based PCPs.
SIGACT News, 2005

A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover.
SIAM J. Comput., 2005

Hardness of approximating the shortest vector problem in lattices.
J. ACM, 2005

Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?
Electron. Colloquium Comput. Complex., 2005

On earthmover distance, metric labeling, and 0-extension
Electron. Colloquium Comput. Complex., 2005

Nonembeddability theorems via Fourier analysis.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

On the Unique Games Conjecture.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

Hardness of Max 3SAT with No Mixed Clauses.
Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004
Cell-probe lower bounds for the partial match problem.
J. Comput. Syst. Sci., 2004

A new PCP outer verifier with applications to homogeneous linear equations and max-bisection.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003
Fitting algebraic curves to noisy data.
J. Comput. Syst. Sci., 2003

Hardness of Approximating the Shortest Vector Problem in High L<sub>p</sub> Norms.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

Vertex Cover Might be Hard to Approximate to within 2-\varepsilon.
Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

A Strong Inapproximability Gap for a Generalization of Minimum Bisection.
Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

Near-Optimal Lower Bounds on the Multi-Party Communication Complexity of Set Disjointness.
Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002
Parameterized complexity of finding subgraphs with hereditary properties.
Theor. Comput. Sci., 2002

Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-epsilon)
Electron. Colloquium Comput. Complex., 2002

On the power of unique 2-prover 1-round games.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Hardness results for approximate hypergraph coloring.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Hardness Results for Coloring 3 -Colorable 3 -Uniform Hypergraphs.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

2001
Evasiveness of Subgraph Containment and Related Properties.
SIAM J. Comput., 2001

Improved Inaproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001