Subhash A. Khot, Ph.D. - Publications

Affiliations: 
2003 Princeton University, Princeton, NJ 
Area:
Uses of randomness in complexity theory and algorithms; Efficient algorithms for finding approximate solutions to NP-hard problems (or proving that they don't exist); Cryptography.

28 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2019 Bhangale A, Khot S. UG-hardness to NP-hardness by losing half Electronic Colloquium On Computational Complexity. 26: 4. DOI: 10.4230/Lipics.Ccc.2019.3  0.301
2017 Khot S, Saket R. Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors Siam Journal On Computing. 46: 235-271. DOI: 10.1137/15100240X  0.349
2015 Khot SA, Vishnoi NK. The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into ℓ1 Journal of the Acm. 62: 8. DOI: 10.1145/2629614  0.39
2014 Khot SA, Popat P, Vishnoi NK. Almost polynomial factor hardness for closest vector problem with preprocessing Siam Journal On Computing. 43: 1184-1205. DOI: 10.1137/130919623  0.425
2014 Austrin P, Khot S. A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem Ieee Transactions On Information Theory. 60: 6636-6645. DOI: 10.1109/Tit.2014.2340869  0.311
2013 Khot S, Moshkovitz D. NP-Hardness of approximately solving linear equations over reals Siam Journal On Computing. 42: 752-791. DOI: 10.1137/110846415  0.319
2013 Khot S, Naor A. Sharp kernel clustering algorithms and their associated Grothendieck inequalities Random Structures and Algorithms. 42: 269-300. DOI: 10.1002/Rsa.20398  0.347
2012 Khot SA, Popat P, Vishnoi NK. 2 log1-εn hardness for the closest vector problem with preprocessing Proceedings of the Annual Acm Symposium On Theory of Computing. 277-288. DOI: 10.1145/2213977.2214004  0.334
2011 Austrin P, Khot S, Safra M. Inapproximability of vertex cover and independent set in bounded degree graphs Theory of Computing. 7: 27-43. DOI: 10.4086/Toc.2011.V007A003  0.348
2011 Khot S, Saket R. On the hardness of learning intersections of two halfspaces Journal of Computer and System Sciences. 77: 129-141. DOI: 10.1016/J.Jcss.2010.06.010  0.391
2011 Alekhnovich M, Khot SA, Kindler G, Vishnoi NK. Hardness of Approximating the Closest Vector Problem with Pre-Processing Computational Complexity. 20: 741-753. DOI: 10.1007/S00037-011-0031-3  0.369
2011 Chakrabarti A, Khot S. Combinatorial theorems about embedding trees on the real line Journal of Graph Theory. 67: 153-168. DOI: 10.1002/Jgt.20608  0.376
2010 Gopalan P, Khot S, Saket R. Hardness of reconstructing multivariate polynomials over finite fields Siam Journal On Computing. 39: 2598-2621. DOI: 10.1137/070705258  0.354
2009 Karloff H, Khot S, Mehta A, Rabani Y. On Earthmover Distance, Metric Labeling, and 0-Extension Siam Journal On Computing. 39: 371-387. DOI: 10.1137/070685671  0.445
2009 Feldman V, Gopalan P, Khot S, Ponnuswami AK. On Agnostic Learning of Parities, Monomials, and Halfspaces Siam Journal On Computing. 39: 606-645. DOI: 10.1137/070684914  0.311
2009 Khot S, Naor A. Approximate kernel clustering Mathematika. 55: 129-165. DOI: 10.1112/S002557930000098X  0.411
2008 Khot S, Naor A. Linear equations modulo 2 and the L1 diameter of convex bodies Siam Journal On Computing. 38: 1448-1463. DOI: 10.1137/070691140  0.423
2008 Khot S, Regev O. Vertex cover might be hard to approximate to within 2 - ε Journal of Computer and System Sciences. 74: 335-349. DOI: 10.1016/J.Jcss.2007.06.019  0.373
2007 Khot S, Kindler G, Mossel E, O'Donnell R. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? Siam Journal On Computing. 37: 319-357. DOI: 10.1137/S0097539705447372  0.409
2007 Chakrabarti A, Khot S. Improved lower bounds on the randomized complexity of graph properties Random Structures and Algorithms. 30: 427-440. DOI: 10.1002/Rsa.V30:3  0.387
2006 Khot S. Ruling Out PTAS for Graph Min-Bisection, Dense k-Subgraph, and Bipartite Clique Siam Journal On Computing. 36: 1025-1071. DOI: 10.1137/S0097539705447037  0.466
2006 Khot S. Hardness of approximating the Shortest Vector Problem in high ℓp norms Journal of Computer and System Sciences. 72: 206-219. DOI: 10.1016/J.Jcss.2005.07.002  0.368
2005 Håstad J, Khot S. Query efficient PCPs with perfect completeness Theory of Computing. 1: 119-148. DOI: 10.4086/Toc.2005.V001A007  0.368
2005 Khot S. Hardness of approximating the shortest vector problem in lattices Journal of the Acm. 52: 789-808. DOI: 10.1145/1089023.1089027  0.453
2005 Khot S. Guest column: inapproximability results via Long Code based PCPs Sigact News. 36: 25-42. DOI: 10.1145/1067309.1067318  0.369
2005 Dinur I, Guruswami V, Khot S, Regev O. A new multilayered PCP and the hardness of hypergraph vertex cover Siam Journal On Computing. 34: 1129-1146. DOI: 10.1137/S0097539704443057  0.424
2004 Jayram TS, Khot S, Kumar R, Rabani Y. Cell-probe lower bounds for the partial match problem Journal of Computer and System Sciences. 69: 435-447. DOI: 10.1016/J.Jcss.2004.04.006  0.403
2002 Chakrabarti A, Khot S, Shi Y. Evasiveness of Subgraph Containment and Related Properties Siam Journal On Computing. 31: 866-875. DOI: 10.1137/S0097539700382005  0.39
Show low-probability matches.