Subhash Khot

	2012
92		Subhash Khot, Preyas Popat, Nisheeth K. Vishnoi: 2log1-ε n hardness for the closest vector problem with preprocessing. STOC 2012: 277-288
	2011
91		Subhash Khot, Muli Safra: A Two Prover One Round Game with Strong Soundness. FOCS 2011: 648-657
90		Per Austrin, Subhash Khot: A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem. ICALP (1) 2011: 474-485
89		Subhash Khot, Dana Moshkovitz: NP-hardness of approximately solving linear equations over reals. STOC 2011: 413-420
88		Subhash Khot, Assaf Naor: Grothendieck-type inequalities in combinatorial optimization CoRR abs/1108.2464: (2011)
87		Subhash Khot, Preyas Popat, Nisheeth K. Vishnoi: $2^{\log^{1-\eps} n}$ Hardness for Closest Vector Problem with Preprocessing CoRR abs/1109.2176: (2011)
86		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)
85		Subhash Khot, Preyas Popat, Nisheeth K. Vishnoi: 2log1-έn Hardness for Closest Vector Problem with Preprocessing. Electronic Colloquium on Computational Complexity (ECCC) 18: 119 (2011)
84		Subhash Khot, Rishi Saket: On the hardness of learning intersections of two halfspaces. J. Comput. Syst. Sci. 77(1): 129-141 (2011)
83		Amit Chakrabarti, Subhash Khot: Combinatorial theorems about embedding trees on the real line. Journal of Graph Theory 67(2): 153-168 (2011)
82		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)
	2010
81		Subhash Khot, Preyas Popat, Rishi Saket: Approximate Lasserre Integrality Gap for Unique Games. APPROX-RANDOM 2010: 298-311
80		Irit Dinur, Subhash Khot, Will Perkins, Muli Safra: Hardness of Finding Independent Sets in Almost 3-Colorable Graphs. FOCS 2010: 212-221
79		Nikhil Bansal, Subhash Khot: Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems. ICALP (1) 2010: 250-261
78		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
77		Subhash Khot: On the Unique Games Conjecture (Invited Survey). IEEE Conference on Computational Complexity 2010: 99-121
76		Subhash Khot, Assaf Naor: Sharp Kernel Clustering Algorithms and Their Associated Grothendieck Inequalities. SODA 2010: 664-683
75		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)
74		Per Austrin, Subhash Khot: A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem CoRR abs/1010.1481: (2010)
73		Subhash Khot, Dana Moshkovitz: NP-Hardness of Approximately Solving Linear Equations Over Reals. Electronic Colloquium on Computational Complexity (ECCC) 17: 112 (2010)
72		Dana Moshkovitz, Subhash Khot: Hardness of Approximately Solving Linear Equations Over Reals. Electronic Colloquium on Computational Complexity (ECCC) 17: 53 (2010)
71		Parikshit Gopalan, Subhash Khot, Rishi Saket: Hardness of Reconstructing Multivariate Polynomials over Finite Fields. SIAM J. Comput. 39(6): 2598-2621 (2010)
	2009
70		Nikhil Bansal, Subhash Khot: Optimal Long Code Test with One Free Bit. FOCS 2009: 453-462
69		Subhash Khot, Rishi Saket: SDP Integrality Gaps with Local ell_1-Embeddability. FOCS 2009: 565-574
68		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
67		Subhash Khot, Assaf Naor: Sharp kernel clustering algorithms and their associated Grothendieck inequalities CoRR abs/0906.4816: (2009)
66		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)
65		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)
64		Subhash Khot, Ryan O'Donnell: SDP Gaps and UGC-hardness for Max-Cut-Gain. Theory of Computing 5(1): 83-117 (2009)
	2008
63		Subhash Khot, Ashok Kumar Ponnuswami: Minimizing Wide Range Regret with Time Selection Functions. COLT 2008: 81-86
62		Subhash Khot, Rishi Saket: Hardness of Minimizing and Learning DNF Expressions. FOCS 2008: 231-240
61		Subhash Khot, Assaf Naor: Approximate Kernel Clustering. FOCS 2008: 561-570
60		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
59		Subhash Khot, Rishi Saket: On hardness of learning intersection of two halfspaces. STOC 2008: 345-354
58		Subhash Khot, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta: Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions. Algorithmica 52(1): 3-18 (2008)
57		Subhash Khot, Assaf Naor: Approximate kernel clustering CoRR abs/0807.4626: (2008)
56		Subhash Khot, Oded Regev: Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci. 74(3): 335-349 (2008)
55		Subhash Khot, Assaf Naor: Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies. SIAM J. Comput. 38(4): 1448-1463 (2008)
	2007
54		Subhash Khot, Ashok Kumar Ponnuswami: Approximation Algorithms for the Max-Min Allocation Problem. APPROX-RANDOM 2007: 204-217
53		Subhash Khot, Rishi Saket: Hardness of Embedding Metric Spaces of Equal Size. APPROX-RANDOM 2007: 218-227
52		Subhash Khot, Assaf Naor: Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies. FOCS 2007: 318-328
51		Parikshit Gopalan, Subhash Khot, Rishi Saket: Hardness of Reconstructing Multivariate Polynomials over Finite Fields. FOCS 2007: 349-359
50		Parikshit Gopalan, Subhash Khot, Rishi Saket: Hardness of Reconstructing Multivariate Polynomials over Finite Fields. Electronic Colloquium on Computational Complexity (ECCC) 14(073): (2007)
49		Amit Chakrabarti, Subhash Khot: Improved lower bounds on the randomized complexity of graph properties. Random Struct. Algorithms 30(3): 427-440 (2007)
48		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)
	2006
47		Subhash Khot, Ryan O'Donnell: SDP gaps and UGC-hardness for MAXCUTGAIN. FOCS 2006: 217-226
46		Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami: New Results for Learning Noisy Parities and Halfspaces. FOCS 2006: 563-574
45		Subhash Khot, Ashok Kumar Ponnuswami: Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion. ICALP (1) 2006: 226-237
44		Subhash Khot, Rishi Saket: A 3-Query Non-Adaptive PCP with Perfect Completeness. IEEE Conference on Computational Complexity 2006: 159-169
43		Nikhil R. Devanur, Subhash Khot, Rishi Saket, Nisheeth K. Vishnoi: Integrality gaps for sparsest cut and minimum linear arrangement problems. STOC 2006: 537-546
42		Howard J. Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani: On earthmover distance, metric labeling, and 0-extension. STOC 2006: 547-556
41		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)
40		Subhash Khot: Hardness of approximating the Shortest Vector Problem in high lp norms. J. Comput. Syst. Sci. 72(2): 206-219 (2006)
39		Subhash Khot: Ruling Out PTAS for Graph Min-Bisection, Dense k-Subgraph, and Bipartite Clique. SIAM J. Comput. 36(4): 1025-1071 (2006)
	2005
38		Subhash Khot, Assaf Naor: Nonembeddability theorems via Fourier analysis. FOCS 2005: 101-112
37		Mikhail Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth K. Vishnoi: Hardness of Approximating the Closest Vector Problem with Pre-Processing. FOCS 2005: 216-225
36		Subhash Khot: On the Unique Games Conjecture. FOCS 2005: 3
35		Subhash Khot, Nisheeth K. Vishnoi: The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into l1. FOCS 2005: 53-62
34		Venkatesan Guruswami, Subhash Khot: Hardness of Max 3SAT with No Mixed Clauses. IEEE Conference on Computational Complexity 2005: 154-162
33		Subhash Khot, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta: Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions. WINE 2005: 92-101
32		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)
31		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)
30		Subhash Khot: Hardness of approximating the shortest vector problem in lattices. J. ACM 52(5): 789-808 (2005)
29		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)
28		Subhash Khot: Guest column: inapproximability results via Long Code based PCPs. SIGACT News 36(2): 25-42 (2005)
27		Johan Håstad, Subhash Khot: Query Efficient PCPs with Perfect Completeness. Theory of Computing 1(1): 119-148 (2005)
	2004
26		Subhash Khot: Hardness of Approximating the Shortest Vector Problem in Lattices. FOCS 2004: 126-135
25		Subhash Khot: Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique. FOCS 2004: 136-145
24		Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell: Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs? FOCS 2004: 146-154
23		Jonas Holmerin, Subhash Khot: A new PCP outer verifier with applications to homogeneous linear equations and max-bisection. STOC 2004: 11-20
22		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)
	2003
21		Subhash Khot: Hardness of Approximating the Shortest Vector Problem in High Lp Norms. FOCS 2003: 290-297
20		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
19		Jonas Holmerin, Subhash Khot: A Strong Inapproximability Gap for a Generalization of Minimum Bisection. IEEE Conference on Computational Complexity 2003: 371-378
18		Subhash Khot, Oded Regev: Vertex Cover Might be Hard to Approximate to within 2-\varepsilon. IEEE Conference on Computational Complexity 2003: 379-
17		Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev: A new multilayered PCP and the hardness of hypergraph vertex cover. STOC 2003: 595-601
16		T. S. Jayram, Subhash Khot, Ravi Kumar, Yuval Rabani: Cell-probe lower bounds for the partial match problem. STOC 2003: 667-672
15		Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev: A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover CoRR cs.CC/0304026: (2003)
14		Sanjeev Arora, Subhash Khot: Fitting algebraic curves to noisy data. J. Comput. Syst. Sci. 67(2): 325-340 (2003)
	2002
13		Subhash Khot: Hardness Results for Coloring 3 -Colorable 3 -Uniform Hypergraphs. FOCS 2002: 23-32
12		Subhash Khot: On the Power of Unique 2-Prover 1-Round Games. IEEE Conference on Computational Complexity 2002: 25
11		Sanjeev Arora, Subhash Khot: Fitting algebraic curves to noisy data. STOC 2002: 162-169
10		Subhash Khot: Hardness results for approximate hypergraph coloring. STOC 2002: 351-359
9		Subhash Khot: On the power of unique 2-prover 1-round games. STOC 2002: 767-775
8		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)
7		Subhash Khot, Venkatesh Raman: Parameterized complexity of finding subgraphs with hereditary properties. Theor. Comput. Sci. 289(2): 997-1008 (2002)
	2001
6		Subhash Khot: Improved Inaproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring. FOCS 2001: 600-609
5		Johan Håstad, Subhash Khot: Query Efficient PCPs with Perfect Completeness. FOCS 2001: 610-619
4		Amit Chakrabarti, Subhash Khot: Improved Lower Bounds on the Randomized Complexity of Graph Properties. ICALP 2001: 285-296
3		Amit Chakrabarti, Subhash Khot, Yaoyun Shi: Evasiveness of Subgraph Containment and Related Properties. STACS 2001: 110-120
2		Amit Chakrabarti, Subhash Khot, Yaoyun Shi: Evasiveness of Subgraph Containment and Related Properties. SIAM J. Comput. 31(3): 866-875 (2001)
	2000
1		Subhash Khot, Venkatesh Raman: Parameterized Complexity of Finding Subgraphs with Hereditary Properties. COCOON 2000: 137-147

Coauthor Index

1	Ashkan Aazami	[75]
2	Mikhail Alekhnovich	[37] [86]
3	Matthew Andrews	[75]
4	Sanjeev Arora	[11] [14] [60] [75]
5	Per Austrin	[68] [74] [82] [90]
6	Nikhil Bansal	[70] [79]
7	Amit Chakrabarti	[2] [3] [4] [20] [49] [83]
8	Moses Charikar	[75]
9	Dev Desai	[75]
10	Nikhil R. Devanur	[43]
11	Irit Dinur	[8] [15] [17] [29] [80]
12	Vitaly Feldman	[41] [46] [65]
13	Parikshit Gopalan	[41] [46] [50] [51] [65] [71]
14	Igor Gorodezky	[75]
15	Venkatesan Guruswami	[8] [15] [17] [29] [34] [78]
16	Prahladh Harsha	[75]
17	Johan Håstad	[5] [27]
18	Jonas Holmerin	[19] [23]
19	Geetha Jagannathan	[75]
20	T. S. Jayram (Jayram S. Thathachar)	[16] [22]
21	Howard J. Karloff	[32] [42] [66]
22	Guy Kindler	[24] [31] [37] [48] [86]
23	Alexandra Kolla	[60]
24	Alexander S. Kulikov	[75]
25	Ravi Kumar (S. Ravi Kumar)	[16] [22]
26	Richard J. Lipton	[33] [58]
27	Evangelos Markakis (Vangelis Markakis)	[33] [58]
28	Aranyak Mehta	[32] [33] [42] [58] [66]
29	Darakhshan J. Mir	[75]
30	Dana Moshkovitz	[72] [73] [75] [89]
31	Elchanan Mossel	[24] [31] [48]
32	Assaf Naor	[38] [52] [55] [57] [61] [67] [76] [88]
33	Alantha Newman	[75]
34	Aleksandar Nikolov	[75]
35	Ryan O'Donnell	[24] [31] [47] [48] [64] [78]
36	Will Perkins	[80]
37	Ashok Kumar Ponnuswami	[41] [45] [46] [54] [63] [65]
38	Preyas Popat	[78] [81] [85] [87] [92]
39	David Pritchard	[75]
40	Yuval Rabani	[16] [22] [32] [42] [66]
41	Venkatesh Raman	[1] [7]
42	Oded Regev	[15] [17] [18] [29] [56]
43	Shmuel Safra (Muli Safra)	[68] [80] [82] [91]
44	Rishi Saket	[43] [44] [50] [51] [53] [59] [62] [69] [71] [81] [84]
45	Yaoyun Shi	[2] [3]
46	Gwen Spencer	[75]
47	David Steurer	[60]
48	Xiaodong Sun	[20]
49	Madhur Tulsiani	[60] [78]
50	Nisheeth K. Vishnoi	[35] [37] [43] [60] [85] [86] [87] [92]
51	Yi Wu	[78]
52	Lisa Zhang	[75]

Colors in the list of coauthors

Last update Fri Jun 1 15:44:53 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page