Subhash Khot

Most-cited papers

Unique games on expanding constraint graphs are easy: extended abstract
Sanjeev Arora, Subhash Khot, A. Kolla, David Steurer +2 more
2008Symposium on the Theory of Computing140 citations Open access
Semantic Scholar
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs
Per Austrin, Subhash Khot, M. Safra
20092009 24th Annual IEEE Conference on Computational Complexity132 citations Open access
Semantic Scholar
Optimal Long Code Test with One Free Bit
N. Bansal, Subhash Khot
20092009 50th Annual IEEE Symposium on Foundations of Computer Science112 citations
Semantic Scholar
Towards a proof of the 2-to-1 games conjecture?
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer +1 more
2018Electron. Colloquium Comput. Complex.107 citations
Semantic Scholar
On Agnostic Learning of Parities, Monomials, and Halfspaces
V. Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami
2009SIAM journal on computing (Print)99 citations
Semantic Scholar
Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems
N. Bansal, Subhash Khot
2010International Colloquium on Automata, Languages and Programming97 citations Open access
Semantic Scholar
On independent sets, 2-to-2 games, and Grassmann graphs
Subhash Khot, Dor Minzer, M. Safra
2017Electron. Colloquium Comput. Complex.96 citations
Semantic Scholar
On Monotonicity Testing and Boolean Isoperimetric Type Theorems
Subhash Khot, Dor Minzer, M. Safra
2015IEEE Annual Symposium on Foundations of Computer Science94 citations
Semantic Scholar
Grothendieck‐Type Inequalities in Combinatorial Optimization
Subhash Khot, A. Naor
2011arXiv.org90 citations Open access
Semantic Scholar
On non-optimally expanding sets in Grassmann graphs
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer +1 more
2018Israel Journal of Mathematics71 citations
Semantic Scholar
Vertex cover might be hard to approximate to within 2-epsilon
Subhash Khot, O. Regev
2008Journal of computer and system sciences (Print)63 citations
Semantic Scholar
SDP Integrality Gaps with Local ell_1-Embeddability
Subhash Khot, Rishi Saket
20092009 50th Annual IEEE Symposium on Foundations of Computer Science55 citations
Semantic Scholar
Inapproximability of NP-complete Problems, Discrete Fourier Analysis, and Geometry
Subhash Khot
201148 citations
Semantic Scholar
Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies
Subhash Khot, A. Naor
2008IEEE Annual Symposium on Foundations of Computer Science48 citations Open access
Semantic Scholar
SDP Integrality Gaps with Local̀ 1-Embeddability Subhash Khot
Subhash Khot, Rishi Saket
200947 citations
Semantic Scholar
Approximate Kernel Clustering
Subhash Khot, A. Naor
20082008 49th Annual IEEE Symposium on Foundations of Computer Science39 citations Open access
Semantic Scholar
Hardness of Minimizing and Learning DNF Expressions
Subhash Khot, Rishi Saket
20082008 49th Annual IEEE Symposium on Foundations of Computer Science37 citations
Semantic Scholar
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem
Per Austrin, Subhash Khot
2010IEEE Transactions on Information Theory35 citations Open access
Semantic Scholar
A characterization of strong approximation resistance
Subhash Khot, Madhur Tulsiani, P. Worah
2013Electron. Colloquium Comput. Complex.31 citations
Semantic Scholar
Inapproximability Results for Computational Problems on Lattices
Subhash Khot
2010The LLL Algorithm30 citations
Semantic Scholar
On the hardness of learning intersections of two halfspaces
Subhash Khot, Rishi Saket
2011Journal of computer and system sciences (Print)29 citations Open access
Semantic Scholar
A Two Prover One Round Game with Strong Soundness
Subhash Khot, M. Safra
2011IEEE Annual Symposium on Foundations of Computer Science28 citations Open access
Semantic Scholar
Sharp kernel clustering algorithms and their associated Grothendieck inequalities
Subhash Khot, A. Naor
2009ACM-SIAM Symposium on Discrete Algorithms28 citations
Semantic Scholar
Small Set Expansion in The Johnson Graph
Subhash Khot, Dor Minzer, Dana Moshkovitz, S. Safra
2018Electron. Colloquium Comput. Complex.26 citations
Semantic Scholar
An Invariance Principle for the Multi-slice, with Applications
M. Braverman, Subhash Khot, Noam Lifshitz, Dor Minzer
2021IEEE Annual Symposium on Foundations of Computer Science25 citations Open access
Semantic Scholar
Hardness of Finding Independent Sets in Almost q-Colorable Graphs
Irit Dinur, Subhash Khot, Will Perkins, M. Safra
2010IEEE Annual Symposium on Foundations of Computer Science25 citations
Semantic Scholar
On a Cut-Matching Game for the Sparsest Cut Problem
R. Khandekar, Subhash Khot, Lorenzo Orecchia, Nisheeth K. Vishnoi
200725 citations
Semantic Scholar
On approximability of satisfiable k-CSPs: I
Amey Bhangale, Subhash Khot, Dor Minzer
2022Computational Complexity23 citations Open access
Semantic Scholar
Almost polynomial factor inapproximability for parameterized k-clique
S. KarthikC, Subhash Khot
2021Cybersecurity and Cyberforensics Conference22 citations
Semantic Scholar
Candidate hard unique game
Subhash Khot, Dana Moshkovitz
2016Symposium on the Theory of Computing22 citations
Semantic Scholar
An Õ(n) Queries Adaptive Tester for Unateness
Subhash Khot, Igor Shinkar
2016Electron. Colloquium Comput. Complex.22 citations
Semantic Scholar
On Approximability of Satisfiable k-CSPs: II
Amey Bhangale, Subhash Khot, Dor Minzer
2023Symposium on the Theory of Computing21 citations Open access
Semantic Scholar
On hardness of learning intersection of two halfspaces
Subhash Khot, Rishi Saket
2008Symposium on the Theory of Computing21 citations
Semantic Scholar
Optimal inapproximability of satisfiable k-LIN over non-abelian groups
Amey Bhangale, Subhash Khot
2020Electron. Colloquium Comput. Complex.20 citations Open access
Semantic Scholar
On Approximability of Satisfiable k-CSPs: III
Amey Bhangale, Subhash Khot, Dor Minzer
2023Symposium on the Theory of Computing19 citations Open access
Semantic Scholar
On Rich $2$-to-$1$ Games
M. Braverman, Subhash Khot, Dor Minzer
2019Electron. Colloquium Comput. Complex.19 citations
Semantic Scholar
UG-hardness to NP-hardness by losing half
Amey Bhangale, Subhash Khot
2019Electron. Colloquium Comput. Complex.18 citations
Semantic Scholar
NP-hardness of approximately solving linear equations over reals
Subhash Khot, Dana Moshkovitz
2011SIAM journal on computing (Print)18 citations Open access
Semantic Scholar
Approximate Lasserre Integrality Gap for Unique Games
Subhash Khot, P. Popat, Rishi Saket
2010International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques18 citations
Semantic Scholar
Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs
Subhash Khot, Rishi Saket
2013ACM-SIAM Symposium on Discrete Algorithms17 citations
Semantic Scholar
The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into $\ell_1$
Subhash Khot, Nisheeth K. Vishnoi
201316 citations
Semantic Scholar
On Approximability of Satisfiable k-CSPs: IV
Amey Bhangale, Subhash Khot, Dor Minzer
2023Electron. Colloquium Comput. Complex.15 citations Open access
Semantic Scholar
Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with 2log nΩ(1) Colors
Subhash Khot, Rishi Saket
2014Electron. Colloquium Comput. Complex.15 citations
Semantic Scholar
Parallel Repetition for the GHZ Game: Exponential Decay
M. Braverman, Subhash Khot, Dor Minzer
2022IEEE Annual Symposium on Foundations of Computer Science14 citations
Semantic Scholar
Improved Monotonicity Testers via Hypercube Embeddings
M. Braverman, Subhash Khot, Guy Kindler, Dor Minzer
2022Information Technology Convergence and Services13 citations Open access
Semantic Scholar
Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality
E. Kelman, Subhash Khot, Guy Kindler, Dor Minzer +1 more
2020Electron. Colloquium Comput. Complex.12 citations
Semantic Scholar
Approximating CSPs Using LP Relaxation
Subhash Khot, Rishi Saket
2015International Colloquium on Automata, Languages and Programming12 citations
Semantic Scholar
Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with exp(log^{Omega(1)} n) Colors
Subhash Khot, Rishi Saket
2014IEEE Annual Symposium on Foundations of Computer Science12 citations
Semantic Scholar
Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)
P. Harsha, M. Charikar, M. Andrews, Sanjeev Arora +13 more
2010arXiv.org12 citations
Semantic Scholar
A characterization of approximation resistance for even k-partite CSPs
Per Austrin, Subhash Khot
2013Information Technology Convergence and Services11 citations
Semantic Scholar