Subhash Khot

Subhash Khot, Assaf Naor: Sharp kernel clustering algorithms and their associated Grothendieck inequalities. Random Struct. Algorithms 42(3): 269-300 (2013)

Subhash Khot, Muli Safra, Madhur Tulsiani: Towards an optimal query efficient PCP? ITCS 2013: 173-186

Per Austrin, Subhash Khot: A characterization of approximation resistance for even k-partite CSPs. ITCS 2013: 187-196

Per Austrin, Subhash Khot: A Characterization of Approximation Resistance for Even $k$-Partite CSPs. CoRR abs/1301.2731 (2013)

Subhash Khot, Rishi Saket: Hardness of Finding Independent Sets in Almost q-Colorable Graphs. FOCS 2012: 380-389

Subhash Khot, Preyas Popat, Nisheeth K. Vishnoi: 2^{log1-ε n} hardness for the closest vector problem with preprocessing. STOC 2012: 277-288

Subhash Khot, Muli Safra, Madhur Tulsiani: Towards An Optimal Query Efficient PCP? Electronic Colloquium on Computational Complexity (ECCC) 19: 109 (2012)

Subhash Khot, Madhur Tulsiani, Pratik Worah: The Complexity of Somewhat Approximation Resistant Predicates. Electronic Colloquium on Computational Complexity (ECCC) 19: 151 (2012)

Mikhail Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth K. Vishnoi: Hardness of Approximating the Closest Vector Problem with Pre-Processing. Computational Complexity 20(4): 741-753 (2011)

Subhash Khot, Rishi Saket: On the hardness of learning intersections of two halfspaces. J. Comput. Syst. Sci. 77(1): 129-141 (2011)

Amit Chakrabarti, Subhash Khot: Combinatorial theorems about embedding trees on the real line. Journal of Graph Theory 67(2): 153-168 (2011)

Per Austrin, Subhash Khot, Muli Safra: Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs. Theory of Computing 7(1): 27-43 (2011)

Subhash Khot, Muli Safra: A Two Prover One Round Game with Strong Soundness. FOCS 2011: 648-657

Per Austrin, Subhash Khot: A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem. ICALP (1) 2011: 474-485

Subhash Khot, Dana Moshkovitz: NP-hardness of approximately solving linear equations over reals. STOC 2011: 413-420

Subhash Khot, Assaf Naor: Grothendieck-type inequalities in combinatorial optimization. CoRR abs/1108.2464 (2011)

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

Subhash Khot, Preyas Popat, Nisheeth K. Vishnoi: 2^log1-έn Hardness for Closest Vector Problem with Preprocessing. Electronic Colloquium on Computational Complexity (ECCC) 18: 119 (2011)

Parikshit Gopalan, Subhash Khot, Rishi Saket: Hardness of Reconstructing Multivariate Polynomials over Finite Fields. SIAM J. Comput. 39(6): 2598-2621 (2010)

Subhash Khot, Preyas Popat, Rishi Saket: Approximate Lasserre Integrality Gap for Unique Games. APPROX-RANDOM 2010: 298-311

Subhash Khot: On the Unique Games Conjecture (Invited Survey). IEEE Conference on Computational Complexity 2010: 99-121

Irit Dinur, Subhash Khot, Will Perkins, Muli Safra: Hardness of Finding Independent Sets in Almost 3-Colorable Graphs. FOCS 2010: 212-221

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

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

Subhash Khot, Assaf Naor: Sharp Kernel Clustering Algorithms and Their Associated Grothendieck Inequalities. SODA 2010: 664-683

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, Darakhshan J. Mir, Alantha Newman, Aleksandar Nikolov, David Pritchard, Gwen Spencer: Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes). CoRR abs/1002.3864 (2010)

Per Austrin, Subhash Khot: A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem. CoRR abs/1010.1481 (2010)

Dana Moshkovitz, Subhash Khot: Hardness of Approximately Solving Linear Equations Over Reals. Electronic Colloquium on Computational Complexity (ECCC) 17: 53 (2010)

Subhash Khot, Dana Moshkovitz: NP-Hardness of Approximately Solving Linear Equations Over Reals. Electronic Colloquium on Computational Complexity (ECCC) 17: 112 (2010)

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

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

Subhash Khot, Ryan O'Donnell: SDP Gaps and UGC-hardness for Max-Cut-Gain. Theory of Computing 5(1): 83-117 (2009)

Per Austrin, Subhash Khot, Muli Safra: Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs. IEEE Conference on Computational Complexity 2009: 74-80

Nikhil Bansal, Subhash Khot: Optimal Long Code Test with One Free Bit. FOCS 2009: 453-462

Subhash Khot, Rishi Saket: SDP Integrality Gaps with Local ell_1-Embeddability. FOCS 2009: 565-574

Subhash Khot, Assaf Naor: Sharp kernel clustering algorithms and their associated Grothendieck inequalities. CoRR abs/0906.4816 (2009)

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

Subhash Khot, Oded Regev: Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci. 74(3): 335-349 (2008)

Subhash Khot, Assaf Naor: Linear Equations Modulo 2 and the L₁ Diameter of Convex Bodies. SIAM J. Comput. 38(4): 1448-1463 (2008)

Subhash Khot, Ashok Kumar Ponnuswami: Minimizing Wide Range Regret with Time Selection Functions. COLT 2008: 81-86

Subhash Khot, Rishi Saket: Hardness of Minimizing and Learning DNF Expressions. FOCS 2008: 231-240

Subhash Khot, Assaf Naor: Approximate Kernel Clustering. FOCS 2008: 561-570

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

Subhash Khot, Rishi Saket: On hardness of learning intersection of two halfspaces. STOC 2008: 345-354

Subhash Khot, Assaf Naor: Approximate kernel clustering. CoRR abs/0807.4626 (2008)

Amit Chakrabarti, Subhash Khot: Improved lower bounds on the randomized complexity of graph properties. Random Struct. Algorithms 30(3): 427-440 (2007)

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

Subhash Khot, Ashok Kumar Ponnuswami: Approximation Algorithms for the Max-Min Allocation Problem. APPROX-RANDOM 2007: 204-217

Subhash Khot, Rishi Saket: Hardness of Embedding Metric Spaces of Equal Size. APPROX-RANDOM 2007: 218-227

Subhash Khot, Assaf Naor: Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies. FOCS 2007: 318-328

Parikshit Gopalan, Subhash Khot, Rishi Saket: Hardness of Reconstructing Multivariate Polynomials over Finite Fields. FOCS 2007: 349-359

Parikshit Gopalan, Subhash Khot, Rishi Saket: Hardness of Reconstructing Multivariate Polynomials over Finite Fields. Electronic Colloquium on Computational Complexity (ECCC) 14(073) (2007)

Subhash Khot: Hardness of approximating the Shortest Vector Problem in high l_p norms. J. Comput. Syst. Sci. 72(2): 206-219 (2006)

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

Subhash Khot, Rishi Saket: A 3-Query Non-Adaptive PCP with Perfect Completeness. IEEE Conference on Computational Complexity 2006: 159-169

Subhash Khot, Ryan O'Donnell: SDP gaps and UGC-hardness for MAXCUTGAIN. FOCS 2006: 217-226

Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami: New Results for Learning Noisy Parities and Halfspaces. FOCS 2006: 563-574

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

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

Howard J. Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani: On earthmover distance, metric labeling, and 0-extension. STOC 2006: 547-556

Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami: New Results for Learning Noisy Parities and Halfspaces. Electronic Colloquium on Computational Complexity (ECCC) 13(059) (2006)

Subhash Khot: Hardness of approximating the shortest vector problem in lattices. J. ACM 52(5): 789-808 (2005)

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

Subhash Khot: Guest column: inapproximability results via Long Code based PCPs. SIGACT News 36(2): 25-42 (2005)

Johan Håstad, Subhash Khot: Query Efficient PCPs with Perfect Completeness. Theory of Computing 1(1): 119-148 (2005)

Venkatesan Guruswami, Subhash Khot: Hardness of Max 3SAT with No Mixed Clauses. IEEE Conference on Computational Complexity 2005: 154-162

Subhash Khot: On the Unique Games Conjecture. FOCS 2005: 3

Subhash Khot, Nisheeth K. Vishnoi: The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into l₁. FOCS 2005: 53-62

Subhash Khot, Assaf Naor: Nonembeddability theorems via Fourier analysis. FOCS 2005: 101-112

Mikhail Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth K. Vishnoi: Hardness of Approximating the Closest Vector Problem with Pre-Processing. FOCS 2005: 216-225

Subhash Khot, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta: Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions. WINE 2005: 92-101

Howard J. Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani: On earthmover distance, metric labeling, and 0-extension. Electronic Colloquium on Computational Complexity (ECCC)(064) (2005)

Guy Kindler, Ryan O'Donnell, Subhash Khot, Elchanan Mossel: Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs? Electronic Colloquium on Computational Complexity (ECCC)(101) (2005)

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

Subhash Khot: Hardness of Approximating the Shortest Vector Problem in Lattices. FOCS 2004: 126-135

Subhash Khot: Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique. FOCS 2004: 136-145

Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell: Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs? FOCS 2004: 146-154

Jonas Holmerin, Subhash Khot: A new PCP outer verifier with applications to homogeneous linear equations and max-bisection. STOC 2004: 11-20

Sanjeev Arora, Subhash Khot: Fitting algebraic curves to noisy data. J. Comput. Syst. Sci. 67(2): 325-340 (2003)

Amit Chakrabarti, Subhash Khot, Xiaodong Sun: Near-Optimal Lower Bounds on the Multi-Party Communication Complexity of Set Disjointness. IEEE Conference on Computational Complexity 2003: 107-117

Jonas Holmerin, Subhash Khot: A Strong Inapproximability Gap for a Generalization of Minimum Bisection. IEEE Conference on Computational Complexity 2003: 371-378

Subhash Khot, Oded Regev: Vertex Cover Might be Hard to Approximate to within 2-\varepsilon. IEEE Conference on Computational Complexity 2003: 379-

Subhash Khot: Hardness of Approximating the Shortest Vector Problem in High Lp Norms. FOCS 2003: 290-297

Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev: A new multilayered PCP and the hardness of hypergraph vertex cover. STOC 2003: 595-601

T. S. Jayram, Subhash Khot, Ravi Kumar, Yuval Rabani: Cell-probe lower bounds for the partial match problem. STOC 2003: 667-672

Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev: A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover. CoRR cs.CC/0304026 (2003)

Subhash Khot, Venkatesh Raman: Parameterized complexity of finding subgraphs with hereditary properties. Theor. Comput. Sci. 289(2): 997-1008 (2002)

Subhash Khot: On the Power of Unique 2-Prover 1-Round Games. IEEE Conference on Computational Complexity 2002: 25

Subhash Khot: Hardness Results for Coloring 3 -Colorable 3 -Uniform Hypergraphs. FOCS 2002: 23-32

Sanjeev Arora, Subhash Khot: Fitting algebraic curves to noisy data. STOC 2002: 162-169

Subhash Khot: Hardness results for approximate hypergraph coloring. STOC 2002: 351-359

Subhash Khot: On the power of unique 2-prover 1-round games. STOC 2002: 767-775

Irit Dinur, Venkatesan Guruswami, Subhash Khot: Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-epsilon). Electronic Colloquium on Computational Complexity (ECCC)(027) (2002)

Amit Chakrabarti, Subhash Khot, Yaoyun Shi: Evasiveness of Subgraph Containment and Related Properties. SIAM J. Comput. 31(3): 866-875 (2001)

Subhash Khot: Improved Inaproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring. FOCS 2001: 600-609

Johan Håstad, Subhash Khot: Query Efficient PCPs with Perfect Completeness. FOCS 2001: 610-619

Amit Chakrabarti, Subhash Khot: Improved Lower Bounds on the Randomized Complexity of Graph Properties. ICALP 2001: 285-296

Amit Chakrabarti, Subhash Khot, Yaoyun Shi: Evasiveness of Subgraph Containment and Related Properties. STACS 2001: 110-120

Subhash Khot, Venkatesh Raman: Parameterized Complexity of Finding Subgraphs with Hereditary Properties. COCOON 2000: 137-147