Subhash Khot

Q: What Schools Are Affiliated With Subhash Khot

Subhash Khot is affiliated with the following schools: Princeton University, University of Chicago, IIT Bombay, Georgia Tech, New York University

Subhash Khot's AcademicInfluence.com Rankings

Subhash Khot

Computer Science

#1315

World Rank

#1359

Historical Rank

#666

USA Rank

Theoretical Computer Science

#104

World Rank

#104

Historical Rank

#28

USA Rank

Database

#3403

World Rank

#3545

Historical Rank

#627

USA Rank

computer-science Degrees

Download Badge

Computer Science

Subhash Khot's Degrees

PhD Computer Science Princeton University

Similar Degrees You Can Earn

Best Online PhD of Computer Science (Doctorates) 2025

Why Is Subhash Khot Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Subhash Khot is an Indian-American mathematician and theoretical computer scientist who is the Julius Silver Professor of Computer Science in the Courant Institute of Mathematical Sciences at New York University. Khot has contributed to the field of computational complexity, and is best known for his unique games conjecture.

(See a Problem?)

Subhash Khot's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

On the power of unique 2-prover 1-round games (2002) (924)
Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? (2004) (735)
Vertex cover might be hard to approximate to within 2-epsilon (2008) (658)
Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique (2004) (341)
The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into l/sub 1/ (2005) (319)
Vertex cover might be hard to approximate to within 2-/spl epsiv/ (2003) (314)
Hardness of approximating the shortest vector problem in lattices (2004) (234)
Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring (2001) (202)
Near-optimal lower bounds on the multi-party communication complexity of set disjointness (2003) (201)
A new multilayered PCP and the hardness of hypergraph vertex cover (2003) (187)
New Results for Learning Noisy Parities and Halfspaces (2006) (165)
Parameterized complexity of finding subgraphs with hereditary properties (2000) (131)
Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions (2005) (124)
Unique games on expanding constraint graphs are easy: extended abstract (2008) (122)
Nonembeddability theorems via Fourier analysis (2005) (121)
Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion (2018) (114)
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs (2009) (110)
Integrality gaps for sparsest cut and minimum linear arrangement problems (2006) (104)
Optimal Long Code Test with One Free Bit (2009) (97)
On the Unique Games Conjecture (Invited Survey) (2005) (95)
Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems (2010) (86)
Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion (2006) (85)
Hardness results for coloring 3-colorable 3-uniform hypergraphs (2002) (81)
Grothendieck‐Type Inequalities in Combinatorial Optimization (2011) (80)
Towards a proof of the 2-to-1 games conjecture? (2018) (78)
On Agnostic Learning of Parities, Monomials, and Halfspaces (2009) (73)
On Monotonicity Testing and Boolean Isoperimetric Type Theorems (2015) (73)
On independent sets, 2-to-2 games, and Grassmann graphs (2017) (69)
SDP gaps and UGC-hardness for MAXCUTGAIN (2006) (68)
On non-optimally expanding sets in Grassmann graphs (2018) (64)
The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into 1 (Extended Abstract) (2005) (63)
SDP Integrality Gaps with Local ell_1-Embeddability (2009) (55)
SDP Integrality Gaps with Local̀ 1-Embeddability Subhash Khot (2009) (46)
Cell-probe lower bounds for the partial match problem (2003) (45)
Inapproximability of NP-complete Problems, Discrete Fourier Analysis, and Geometry (2011) (44)
Query efficient PCPs with perfect completeness (2001) (43)
Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies (2008) (41)
Hardness of Approximating the Closest Vector Problem with Pre-Processing (2005) (41)
Approximation Algorithms for the Max-Min Allocation Problem (2007) (39)
Approximate Kernel Clustering (2008) (39)
Fitting algebraic curves to noisy data (2002) (35)
Hardness of Minimizing and Learning DNF Expressions (2008) (35)
Hardness of approximating the Shortest Vector Problem in high lp norms (2006) (32)
Hardness of approximating the shortest vector problem in high L/sub p/ norms (2003) (31)
Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-epsilon) (2002) (31)
Hardness of Reconstructing Multivariate Polynomials over Finite Fields (2007) (29)
Sharp kernel clustering algorithms and their associated Grothendieck inequalities (2009) (27)
A new PCP outer verifier with applications to homogeneous linear equations and max-bisection (2004) (27)
A characterization of strong approximation resistance (2013) (27)
Improved lower bounds on the randomized complexity of graph properties (2001) (26)
Hardness results for approximate hypergraph coloring (2002) (26)
Inapproximability Results for Computational Problems on Lattices (2010) (26)
Guest column: inapproximability results via Long Code based PCPs (2005) (25)
A 3-query non-adaptive PCP with perfect completeness (2006) (25)
On earthmover distance, metric labeling, and 0-extension (2006) (25)
Evasiveness of Subgraph Containment and Related Properties (2001) (25)
A Two Prover One Round Game with Strong Soundness (2011) (24)
On the hardness of learning intersections of two halfspaces (2011) (23)
Hardness of Approximation (2016) (22)
Hardness of Max 3SAT with no mixed clauses (2005) (22)
On hardness of learning intersection of two halfspaces (2008) (21)
An Õ(n) Queries Adaptive Tester for Unateness (2016) (20)
Small Set Expansion in The Johnson Graph (2018) (20)
Hardness of Finding Independent Sets in Almost q-Colorable Graphs (2010) (20)
Candidate hard unique game (2016) (18)
On a Cut-Matching Game for the Sparsest Cut Problem (2007) (18)
Approximate Lasserre Integrality Gap for Unique Games (2010) (17)
NP-hardness of approximately solving linear equations over reals (2011) (17)
Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs (2013) (17)
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem (2010) (15)
Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with exp(log^{Omega(1)} n) Colors (2014) (13)
An Invariance Principle for the Multi-slice, with Applications (2021) (12)
Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes) (2010) (11)
Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with 2log nΩ(1) Colors (2014) (11)
UG-hardness to NP-hardness by losing half (2019) (10)
Optimal inapproximability of satisfiable k-LIN over non-abelian groups (2020) (10)
A characterization of approximation resistance for even k-partite CSPs (2013) (10)
On Hardness of Approximating the Parameterized Clique Problem (2016) (9)
On Rich $2$-to-$1$ Games (2019) (9)
2log1-ε n hardness for the closest vector problem with preprocessing (2012) (8)
Hardness of Embedding Metric Spaces of Equal Size (2007) (8)
SDP Gaps for 2-to-1 and Other Label-Cover Variants (2010) (7)
Approximating CSPs Using LP Relaxation (2015) (7)
On approximability of satisfiable k-CSPs: I (2022) (6)
Hardness for Closest Vector Problem with Preprocessing (2011) (6)
Near-optimal approximation algorithm for simultaneous Max-Cut (2018) (6)
Almost polynomial factor inapproximability for parameterized k-clique (2021) (5)
Minimizing Wide Range Regret with Time Selection Functions (2008) (5)
A strong inapproximability gap for a generalization of minimum bisection (2003) (5)
$2^{\log^{1-\eps} n}$ Hardness for Closest Vector Problem with Preprocessing (2011) (4)
A Characterization of Approximation Resistance (2013) (4)
Towards an optimal query efficient PCP? (2013) (4)
Hardness of Bipartite Expansion (2016) (4)
New techniques for probabilistically checkable proofs and inapproximability results (2003) (4)
Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality (2020) (3)
An Improved Dictatorship Test with Perfect Completeness (2017) (3)
Nonembeddability theorems via Fourier analysis Extended abstract (2005) (3)
Chapter 14 Inapproximability Results for Computational Problems on Lattices (2010) (3)
Almost Polynomial Factor Hardness for Closest Vector Problem with Preprocessing (2014) (3)
Improved Monotonicity Testers via Hypercube Embeddings (2022) (2)
Simultaneous max-cut is harder to approximate than max-cut (2020) (2)
The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics (2018) (2)
Improved 3LIN Hardness via Linear Label Cover (2019) (2)
Candidate Lasserre Integrality Gap For Unique Games (2014) (1)
Combinatorial theorems about embedding trees on the real line (2011) (1)
Hardness of Lattice Problems in 'p Norm (2003) (1)
An $\widetilde{O}(n)$ Queries Adaptive Tester for Unateness (2016) (1)
The Complexity of Somewhat Approximation Resistant Predicates (2014) (1)
Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with 2(log n)Ømega(1) Colors (2017) (1)
The Computational Aspect of Risk in Playing Non-Cooperative Games (2007) (0)
Intractability results for some computational problems (2008) (0)
Session details: Session 6A (2005) (0)
Approximate kernel clustering Extended abstract (2008) (0)
The Andoni–Krauthgamer–Razenshteyn Characterization of Sketchable Norms Fails for Sketchable Metrics (2020) (0)
On non-optimally expanding sets in Grassmann graphs (2021) (0)
Guest column: Inapproximability results in long code based on PCPs (2005) (0)
Proceedings Twenty-Second Annual IEEE Conference on Computational Complexity: Preface (2007) (0)
On Approximability of Satisﬁable k -CSPs: I (2022) (0)
On the proof of the 2-to-2 Games Conjecture (2019) (0)
Parallel Repetition for the GHZ Game: Exponential Decay (2022) (0)
On Approximation Resistance of Predicates (Invited Talk) (2013) (0)
Session details: Session 13 (best student paper) (2005) (0)

This paper list is powered by the following services:

Other Resources About Subhash Khot

What Schools Are Affiliated With Subhash Khot?

Subhash Khot is affiliated with the following schools:

Subhash Khot's Academic­Influence.com Rankings

Subhash Khot's Degrees

Similar Degrees You Can Earn

Why Is Subhash Khot Influential?

Subhash Khot's Published Works

Published Works

Other Resources About Subhash Khot

What Schools Are Affiliated With Subhash Khot?

Subhash Khot's AcademicInfluence.com Rankings