Subhash Khot
Affiliations: New York University, NY, USA
According to our database^{1},
Subhash Khot
authored at least 108 papers
between 2001 and 2022.
Collaborative distances:
Collaborative distances:
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Online presence:

on zbmath.org

on id.loc.gov

on cs.nyu.edu
On csauthors.net:
Bibliography
2022
Electron. Colloquium Comput. Complex., 2022
Proceedings of the 37th Computational Complexity Conference, 2022
2021
Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021
2020
Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and LogSobolev Inequality.
Electron. Colloquium Comput. Complex., 2020
Electron. Colloquium Comput. Complex., 2020
2019
Electron. Colloquium Comput. Complex., 2019
Electron. Colloquium Comput. Complex., 2019
Electron. Colloquium Comput. Complex., 2019
Electron. Colloquium Comput. Complex., 2019
The AndoniKrauthgamerRazenshteyn characterization of sketchable norms fails for sketchable metrics.
Proceedings of the Thirtieth Annual ACMSIAM Symposium on Discrete Algorithms, 2019
2018
Electron. Colloquium Comput. Complex., 2018
Electron. Colloquium Comput. Complex., 2018
Proceedings of the TwentyNinth Annual ACMSIAM Symposium on Discrete Algorithms, 2018
2017
Hardness of Coloring 2Colorable 12Uniform Hypergraphs with 2<sup>(log n)<sup>Ømega(1)</sup></sup> Colors.
SIAM J. Comput., 2017
Electron. Colloquium Comput. Complex., 2017
Electron. Colloquium Comput. Complex., 2017
2016
Electron. Colloquium Comput. Complex., 2016
Electron. Colloquium Comput. Complex., 2016
Electron. Colloquium Comput. Complex., 2016
Electron. Colloquium Comput. Complex., 2016
CoRR, 2016
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016
Proceedings of the 24th Annual European Symposium on Algorithms, 2016
2015
The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of NegativeType Metrics into ℓ<sub>1</sub>.
J. ACM, 2015
Electron. Colloquium Comput. Complex., 2015
Electron. Colloquium Comput. Complex., 2015
2014
IEEE Trans. Inf. Theory, 2014
SIAM J. Comput., 2014
Hardness of Coloring 2Colorable 12Uniform Hypergraphs with 2<sup>log n<sup>Ω(1)</sup></sup> Colors.
Electron. Colloquium Comput. Complex., 2014
Electron. Colloquium Comput. Complex., 2014
Hardness of Finding Independent Sets in 2Colorable and Almost 2Colorable Hypergraphs.
Proceedings of the TwentyFifth Annual ACMSIAM Symposium on Discrete Algorithms, 2014
Hardness of Coloring 2Colorable 12Uniform Hypergraphs with exp(log^{Omega(1)} n) Colors.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014
2013
Theory Comput., 2013
SIAM J. Comput., 2013
Sharp kernel clustering algorithms and their associated Grothendieck inequalities.
Random Struct. Algorithms, 2013
Electron. Colloquium Comput. Complex., 2013
Electron. Colloquium Comput. Complex., 2013
Proceedings of the Innovations in Theoretical Computer Science, 2013
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2013
2012
Electron. Colloquium Comput. Complex., 2012
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
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012
2011
Theory Comput., 2011
J. Graph Theory, 2011
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
CoRR, 2011
CoRR, 2011
Comput. Complex., 2011
2010
Proceedings of the LLL Algorithm  Survey and Applications, 2010
Electron. Colloquium Comput. Complex., 2010
Electron. Colloquium Comput. Complex., 2010
Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)
CoRR, 2010
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
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010
Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, 2010
Proceedings of the Approximation, 2010
2009
Theory Comput., 2009
SIAM J. Comput., 2009
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009
2008
SIAM J. Comput., 2008
J. Comput. Syst. Sci., 2008
Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions.
Algorithmica, 2008
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008
Proceedings of the 21st Annual Conference on Learning Theory, 2008
2007
Random Struct. Algorithms, 2007
Electron. Colloquium Comput. Complex., 2007
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007
Proceedings of the Approximation, 2007
Proceedings of the Approximation, 2007
2006
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
Electron. Colloquium Comput. Complex., 2006
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006
Better Inapproximability Results for MaxClique, Chromatic Number and Min3LinDeletion.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006
Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006
2005
Theory Comput., 2005
SIGACT News, 2005
SIAM J. Comput., 2005
J. ACM, 2005
Electron. Colloquium Comput. Complex., 2005
Electron. Colloquium Comput. Complex., 2005
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005
Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005
2004
J. Comput. Syst. Sci., 2004
A new PCP outer verifier with applications to homogeneous linear equations and maxbisection.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004
2003
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
Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003
Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003
NearOptimal Lower Bounds on the MultiParty Communication Complexity of Set Disjointness.
Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003
2002
Theor. Comput. Sci., 2002
Vertex Cover on kUniform Hypergraphs is Hard to Approximate within Factor (k3epsilon)
Electron. Colloquium Comput. Complex., 2002
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002
2001
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