Improved Inaproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring. - Subhash Khot (FOCS, 2001)

Evasiveness of Subgraph Containment and Related Properties. - Amit Chakrabarti; Subhash Khot; Yaoyun Shi (SIAM J. Comput., 2001)

Hardness Results for Coloring 3 -Colorable 3 -Uniform Hypergraphs. - Subhash Khot (FOCS, 2002)

Hardness results for approximate hypergraph coloring. - Subhash Khot (STOC, 2002)

On the power of unique 2-prover 1-round games. - Subhash Khot (STOC, 2002)

Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-epsilon) - Irit Dinur; Venkatesan Guruswami; Subhash Khot (Electron. Colloquium Comput. Complex., 2002)

Parameterized complexity of finding subgraphs with hereditary properties. - Subhash Khot; Venkatesh Raman 001 (Theor. Comput. Sci., 2002)

Near-Optimal Lower Bounds on the Multi-Party Communication Complexity of Set Disjointness. - Amit Chakrabarti; Subhash Khot; Xiaodong Sun (CCC, 2003)

A Strong Inapproximability Gap for a Generalization of Minimum Bisection. - Jonas Holmerin; Subhash Khot (CCC, 2003)

Vertex Cover Might be Hard to Approximate to within 2- varepsilon. - Subhash Khot; Oded Regev 001 (CCC, 2003)

Hardness of Approximating the Shortest Vector Problem in High Lp Norms. - Subhash Khot (FOCS, 2003)

Fitting algebraic curves to noisy data. - Sanjeev Arora; Subhash Khot (J. Comput. Syst. Sci., 2003)

Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique. - Subhash Khot (FOCS, 2004)

A new PCP outer verifier with applications to homogeneous linear equations and max-bisection. - Jonas Holmerin; Subhash Khot (STOC, 2004)

Cell-probe lower bounds for the partial match problem. - T. S. Jayram; Subhash Khot; Ravi Kumar 001; Yuval Rabani (J. Comput. Syst. Sci., 2004)

Hardness of Max 3SAT with No Mixed Clauses. - Venkatesan Guruswami; Subhash Khot (CCC, 2005)

On the Unique Games Conjecture. - Subhash Khot (FOCS, 2005)

Nonembeddability theorems via Fourier analysis. - Subhash Khot; Assaf Naor (FOCS, 2005)

Hardness of approximating the shortest vector problem in lattices. - Subhash Khot (J. ACM, 2005)

A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover. - Irit Dinur; Venkatesan Guruswami; Subhash Khot; Oded Regev 001 (SIAM J. Comput., 2005)

Guest column: inapproximability results via Long Code based PCPs. - Subhash Khot (SIGACT News, 2005)

Query Efficient PCPs with Perfect Completeness. - Johan Håstad; Subhash Khot (Theory Comput., 2005)

A 3-Query Non-Adaptive PCP with Perfect Completeness. - Subhash Khot; Rishi Saket (CCC, 2006)

SDP gaps and UGC-hardness for MAXCUTGAIN. - Subhash Khot; Ryan O'Donnell (FOCS, 2006)

Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion. - Subhash Khot; Ashok Kumar Ponnuswami (ICALP (1), 2006)

Integrality gaps for sparsest cut and minimum linear arrangement problems. - Nikhil R. Devanur; Subhash Khot; Rishi Saket; Nisheeth K. Vishnoi (STOC, 2006)

New Results for Learning Noisy Parities and Halfspaces. - Vitaly Feldman; Parikshit Gopalan; Subhash Khot; Ashok Kumar Ponnuswami (Electron. Colloquium Comput. Complex., 2006)

Hardness of approximating the Shortest Vector Problem in high lp norms. - Subhash Khot (J. Comput. Syst. Sci., 2006)

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

Approximation Algorithms for the Max-Min Allocation Problem. - Subhash Khot; Ashok Kumar Ponnuswami (APPROX-RANDOM, 2007)

Hardness of Embedding Metric Spaces of Equal Size. - Subhash Khot; Rishi Saket (APPROX-RANDOM, 2007)

Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies. - Subhash Khot; Assaf Naor (FOCS, 2007)

Improved lower bounds on the randomized complexity of graph properties. - Amit Chakrabarti; Subhash Khot (Random Struct. Algorithms, 2007)

Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?. - Subhash Khot; Guy Kindler; Elchanan Mossel; Ryan O'Donnell (SIAM J. Comput., 2007)

Minimizing Wide Range Regret with Time Selection Functions. - Subhash Khot; Ashok Kumar Ponnuswami (COLT, 2008)

Approximate Kernel Clustering. - Subhash Khot; Assaf Naor (FOCS, 2008)

Hardness of Minimizing and Learning DNF Expressions. - Subhash Khot; Rishi Saket (FOCS, 2008)

Unique games on expanding constraint graphs are easy: extended abstract. - Sanjeev Arora; Subhash Khot; Alexandra Kolla; David Steurer; Madhur Tulsiani; Nisheeth K. Vishnoi (STOC, 2008)

On hardness of learning intersection of two halfspaces. - Subhash Khot; Rishi Saket (STOC, 2008)

Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions. - Subhash Khot; Richard J. Lipton; Evangelos Markakis; Aranyak Mehta (Algorithmica, 2008)

Vertex cover might be hard to approximate to within 2-epsilon. - Subhash Khot; Oded Regev 001 (J. Comput. Syst. Sci., 2008)

Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies. - Subhash Khot; Assaf Naor (SIAM J. Comput., 2008)

Optimal Long Code Test with One Free Bit. - Nikhil Bansal 001; Subhash Khot (FOCS, 2009)

SDP Integrality Gaps with Local ell_1-Embeddability. - Subhash Khot; Rishi Saket (FOCS, 2009)

On Agnostic Learning of Parities, Monomials, and Halfspaces. - Vitaly Feldman; Parikshit Gopalan; Subhash Khot; Ashok Kumar Ponnuswami (SIAM J. Comput., 2009)

On Earthmover Distance, Metric Labeling, and 0-Extension. - Howard J. Karloff; Subhash Khot; Aranyak Mehta; Yuval Rabani (SIAM J. Comput., 2009)

SDP Gaps and UGC-hardness for Max-Cut-Gain. - Subhash Khot; Ryan O'Donnell (Theory Comput., 2009)

Approximate Lasserre Integrality Gap for Unique Games. - Subhash Khot; Preyas Popat; Rishi Saket (APPROX-RANDOM, 2010)

On the Unique Games Conjecture (Invited Survey). - Subhash Khot (CCC, 2010)

Hardness of Finding Independent Sets in Almost 3-Colorable Graphs. - Irit Dinur; Subhash Khot; Will Perkins 001; Muli Safra (FOCS, 2010)

Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems. - Nikhil Bansal 001; Subhash Khot (ICALP (1), 2010)

SDP Gaps for 2-to-1 and Other Label-Cover Variants. - Venkatesan Guruswami; Subhash Khot; Ryan O'Donnell; Preyas Popat; Madhur Tulsiani; Yi Wu 002 (ICALP (1), 2010)

Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes) - Prahladh Harsha; Moses Charikar; Matthew Andrews; Sanjeev Arora; Subhash Khot; Dana Moshkovitz; Lisa Zhang; Ashkan Aazami; Dev Desai; Igor Gorodezky; Geetha Jagannathan; Alexander S. Kulikov; et al. (CoRR, 2010)

NP-Hardness of Approximately Solving Linear Equations Over Reals. - Subhash Khot; Dana Moshkovitz (Electron. Colloquium Comput. Complex., 2010)

Hardness of Approximately Solving Linear Equations Over Reals. - Dana Moshkovitz; Subhash Khot (Electron. Colloquium Comput. Complex., 2010)

Hardness of Reconstructing Multivariate Polynomials over Finite Fields. - Parikshit Gopalan; Subhash Khot; Rishi Saket (SIAM J. Comput., 2010)

Inapproximability Results for Computational Problems on Lattices. - Subhash Khot (The LLL Algorithm, 2010)

Hardness of Approximating the Closest Vector Problem with Pre-Processing. - Mikhail Alekhnovich; Subhash Khot; Guy Kindler; Nisheeth K. Vishnoi (Comput. Complex., 2011)

Grothendieck-type inequalities in combinatorial optimization - Subhash Khot; Assaf Naor (CoRR, 2011)

$2^{ log^{1- eps} n}$ Hardness for Closest Vector Problem with Preprocessing - Subhash Khot; Preyas Popat; Nisheeth K. Vishnoi (CoRR, 2011)

2log1-έn Hardness for Closest Vector Problem with Preprocessing. - Subhash Khot; Preyas Popat; Nisheeth K. Vishnoi (Electron. Colloquium Comput. Complex., 2011)

On the hardness of learning intersections of two halfspaces. - Subhash Khot; Rishi Saket (J. Comput. Syst. Sci., 2011)

Combinatorial theorems about embedding trees on the real line. - Amit Chakrabarti; Subhash Khot (J. Graph Theory, 2011)

Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs. - Per Austrin; Subhash Khot; Muli Safra (Theory Comput., 2011)

Hardness of Finding Independent Sets in Almost q-Colorable Graphs. - Subhash Khot; Rishi Saket (FOCS, 2012)

2log1-ε n hardness for the closest vector problem with preprocessing. - Subhash Khot; Preyas Popat; Nisheeth K. Vishnoi (STOC, 2012)

Towards An Optimal Query Efficient PCP? - Subhash Khot; Muli Safra; Madhur Tulsiani (Electron. Colloquium Comput. Complex., 2012)

The Complexity of Somewhat Approximation Resistant Predicates. - Subhash Khot; Madhur Tulsiani; Pratik Worah (Electron. Colloquium Comput. Complex., 2012)

On Approximation Resistance of Predicates (Invited Talk). - Subhash Khot (FSTTCS, 2013)

A characterization of approximation resistance for even k-partite CSPs. - Per Austrin; Subhash Khot (ITCS, 2013)

A Characterization of Strong Approximation Resistance. - Subhash Khot; Madhur Tulsiani; Pratik Worah (Electron. Colloquium Comput. Complex., 2013)

A Characterization of Approximation Resistance. - Subhash Khot; Madhur Tulsiani; Pratik Worah (Electron. Colloquium Comput. Complex., 2013)

Sharp kernel clustering algorithms and their associated Grothendieck inequalities. - Subhash Khot; Assaf Naor (Random Struct. Algorithms, 2013)

NP-Hardness of Approximately Solving Linear Equations over Reals. - Subhash Khot; Dana Moshkovitz (SIAM J. Comput., 2013)

A Two-Prover One-Round Game with Strong Soundness. - Subhash Khot; Muli Safra (Theory Comput., 2013)

Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with exp(log^{Omega(1)} n) Colors. - Subhash Khot; Rishi Saket (FOCS, 2014)

Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs. - Subhash Khot; Rishi Saket (SODA, 2014)

Candidate Lasserre Integrality Gap For Unique Games. - Subhash Khot; Dana Moshkovitz (Electron. Colloquium Comput. Complex., 2014)

Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with 2log nΩ(1) Colors. - Subhash Khot; Rishi Saket (Electron. Colloquium Comput. Complex., 2014)

Almost Polynomial Factor Hardness for Closest Vector Problem with Preprocessing. - Subhash Khot; Preyas Popat; Nisheeth K. Vishnoi (SIAM J. Comput., 2014)

A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem. - Per Austrin; Subhash Khot (IEEE Trans. Inf. Theory, 2014)

On Hardness of Approximating the Parameterized Clique Problem. - Subhash Khot; Igor Shinkar (Electron. Colloquium Comput. Complex., 2015)

The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ1. - Subhash Khot; Nisheeth K. Vishnoi (J. ACM, 2015)

Hardness of Bipartite Expansion. - Subhash Khot; Rishi Saket (ESA, 2016)

Hardness of Approximation. - Subhash Khot (ICALP, 2016)

Candidate hard unique game. - Subhash Khot; Dana Moshkovitz (STOC, 2016)

An $ widetilde{O}(n)$ Queries Adaptive Tester for Unateness. - Subhash Khot; Igor Shinkar (CoRR, 2016)

Towards a Proof of the 2-to-1 Games Conjecture? - Irit Dinur; Subhash Khot; Guy Kindler; Dor Minzer; Muli Safra (Electron. Colloquium Comput. Complex., 2016)

On Independent Sets, 2-to-2 Games and Grassmann Graphs. - Subhash Khot; Dor Minzer; Muli Safra (Electron. Colloquium Comput. Complex., 2016)

Approximating CSPs using LP Relaxation. - Subhash Khot; Rishi Saket (Electron. Colloquium Comput. Complex., 2016)

An Õ(n) Queries Adaptive Tester for Unateness. - Subhash Khot; Igor Shinkar (Electron. Colloquium Comput. Complex., 2016)

An Improved Dictatorship Test with Perfect Completeness. - Amey Bhangale; Subhash Khot; Devanathan Thiruvenkatachari (Electron. Colloquium Comput. Complex., 2017)

On Non-Optimally Expanding Sets in Grassmann Graphs. - Irit Dinur; Subhash Khot; Guy Kindler; Dor Minzer; Muli Safra (Electron. Colloquium Comput. Complex., 2017)

Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with 2(log n)Ømega(1) Colors. - Subhash Khot; Rishi Saket (SIAM J. Comput., 2017)

Near-optimal approximation algorithm for simultaneous Max-Cut. - Amey Bhangale; Subhash Khot; Swastik Kopparty; Sushant Sachdeva; Devanathan Thiruvenkatachari (SODA, 2018)

Small Set Expansion in The Johnson Graph. - Subhash Khot; Dor Minzer; Dana Moshkovitz; Muli Safra (Electron. Colloquium Comput. Complex., 2018)

Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion. - Subhash Khot; Dor Minzer; Muli Safra (Electron. Colloquium Comput. Complex., 2018)

On Monotonicity Testing and Boolean Isoperimetric-type Theorems. - Subhash Khot; Dor Minzer; Muli Safra (SIAM J. Comput., 2018)

The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics. - Subhash Khot; Assaf Naor (SODA, 2019)

UG-hardness to NP-hardness by Losing Half. - Amey Bhangale; Subhash Khot (Electron. Colloquium Comput. Complex., 2019)

Simultaneous Max-Cut is harder to approximate than Max-Cut. - Amey Bhangale; Subhash Khot (Electron. Colloquium Comput. Complex., 2019)

On Rich $2$-to-$1$ Games. - Mark Braverman; Subhash Khot; Dor Minzer (Electron. Colloquium Comput. Complex., 2019)

Improved 3LIN Hardness via Linear Label Cover. - Prahladh Harsha; Subhash Khot; Euiwoong Lee; Devanathan Thiruvenkatachari (Electron. Colloquium Comput. Complex., 2019)

Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups. - Amey Bhangale; Subhash Khot (Electron. Colloquium Comput. Complex., 2020)

Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality. - Esty Kelman; Subhash Khot; Guy Kindler; Dor Minzer; Muli Safra (Electron. Colloquium Comput. Complex., 2020)

An Invariance Principle for the Multi-slice, with Applications. - Mark Braverman; Subhash Khot; Noam Lifshitz; Dor Minzer (FOCS, 2021)

Almost Polynomial Factor Inapproximability for Parameterized k-Clique. - Karthik C. S. 001; Subhash Khot (CCC, 2022)

On Approximability of Satisfiable k-CSPs: I. - Amey Bhangale; Subhash Khot; Dor Minzer (Electron. Colloquium Comput. Complex., 2022)

Parallel Repetition for the GHZ Game: Exponential Decay. - Mark Braverman; Subhash Khot; Dor Minzer (Electron. Colloquium Comput. Complex., 2022)

Improved Monotonicity Testers via Hypercube Embeddings. - Mark Braverman; Subhash Khot; Guy Kindler; Dor Minzer (ITCS, 2023)

On Approximability of Satisfiable k-CSPs: II. - Amey Bhangale; Subhash Khot; Dor Minzer (STOC, 2023)

On Approximability of Satisfiable k-CSPs: III. - Amey Bhangale; Subhash Khot; Dor Minzer (STOC, 2023)

Effective Bounds for Restricted 3-Arithmetic Progressions in Fpn. - Amey Bhangale; Subhash Khot; Dor Minzer (CoRR, 2023)

Parallel Repetition of k-Player Projection Games. - Amey Bhangale; Mark Braverman; Subhash Khot; Yang P. Liu; Dor Minzer (Electron. Colloquium Comput. Complex., 2023)

On Approximability of Satisfiable k-CSPs: III. - Amey Bhangale; Subhash Khot; Dor Minzer (Electron. Colloquium Comput. Complex., 2023)

On Approximability of Satisfiable k-CSPs: II. - Amey Bhangale; Subhash Khot; Dor Minzer (Electron. Colloquium Comput. Complex., 2023)

On Approximability of Satisfiable k-CSPs: IV. - Amey Bhangale; Subhash Khot; Dor Minzer (Electron. Colloquium Comput. Complex., 2023)

Effective Bounds for Restricted $3$-Arithmetic Progressions in $ mathbb{F}_p^n$. - Amey Bhangale; Subhash Khot; Dor Minzer (Electron. Colloquium Comput. Complex., 2023)

On Approximability of Satisfiable k-CSPs: VI. - Amey Bhangale; Subhash Khot; Yang P. Liu; Dor Minzer (CoRR, 2024)

On Approximability of Satisfiable k-CSPs: VII. - Amey Bhangale; Subhash Khot; Yang P. Liu; Dor Minzer (CoRR, 2024)

On Approximability of Satisfiable k-CSPs: VI. - Amey Bhangale; Subhash Khot; Yang P. Liu; Dor Minzer (Electron. Colloquium Comput. Complex., 2024)

On Approximability of Satisfiable k-CSPs: VII. - Amey Bhangale; Subhash Khot; Yang P. Liu; Dor Minzer (Electron. Colloquium Comput. Complex., 2024)

Reasonable Bounds for Combinatorial Lines of Length Three. - Amey Bhangale; Subhash Khot; Yang P. Liu; Dor Minzer (Electron. Colloquium Comput. Complex., 2024)

On Approximability of Satisfiable k-CSPs: V. - Amey Bhangale; Subhash Khot; Dor Minzer (Electron. Colloquium Comput. Complex., 2024)

Maximum Span Hypothesis: A Potentially Weaker Assumption than Gap-ETH for Parameterized Complexity. - Karthik C. S. 001; Subhash Khot (SODA, 2025)

Parallel Repetition for 3-Player XOR Games. - Amey Bhangale; Mark Braverman; Subhash Khot; Yang P. Liu; Dor Minzer (Electron. Colloquium Comput. Complex., 2025)

Biased Linearity Testing in the 1% Regime. - Subhash Khot; Kunal Mittal (Electron. Colloquium Comput. Complex., 2025)

On approximability of Satisfiable k-CSPs: I. - Amey Bhangale; Subhash Khot; Dor Minzer (Comput. Complex., 2025)