|
Associate Professor of Computer Science
Email:
Personal Homepage: http://www.cs.nyu.edu/~khot
Selected Works:
Please email me if you are interested in any of the papers I haven't yet uploaded.
PCPs and Hardness of Approximation
SDP gaps and UGC-hardness for MaxCutGain. With Ryan O'Donnell (FOCS 2006).
New results for learning noisy parities and halfspaces. With Vitaly Feldman, Parikshit Gopalan and Ashok Kumar Ponnuswami (FOCS 2006).
Hardness of approximating the closest vector problem with pre-processing. With Misha Alekhnovich, Guy Kindler, Nisheeth Vishnoi (FOCS 2005).
Hardness of approximating the shortest vector problem in lattices. (FOCS 2004, shared the Best Paper Award, invited to JACM)
Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique. (FOCS 2004, invited to SICOMP).
Optimal inapproximability results for MAX-CUT and other two-variable CSPs ? With Guy Kindler, Ryan Odonnell, Elchanan Mossel (FOCS 2004, invited to SICOMP)
A new PCP outer verifier with applications to homogeneous linear equations and max-bisection. With Jonas Holmerin (STOC 2004)
Hardness of approximating the shortest vector problem in high \ell_p norms. (FOCS 2003, Best Student Paper Award, invited to JCSS)
A 3-query non-adaptive PCP with perfect completeness. With Rishi Saket. (Complexity 2006)
Vertex cover might be hard to approximate within 2-\epsilon. With Oded Regev. (Complexity 2003, invited to JCSS)
A strong inapproximability gap for a generalization of minimum bisection. With Jonas Holmerin. (Complexity 2003)
A new multilayered PCP and the hardness of hypergraph vertex cover. With Irit Dinur, Venkatesan Guruswami, Oded Regev (STOC 2003, invited to JCSS, to appear in SICOMP)
Hardness of coloring 3-colorable 3-uniform hypergraphs. (FOCS 2002)
Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-\epsilon). With Irit Dinur, Venkatesan Guruswami (ECCC Report TR02-027)
Hardness results for approximate hypergraph coloring. (STOC 2002)On the power of unique 2-prover 1-round games. (STOC/Complexity joint session, 2002)
Improved inapproximability results for maxclique, chromatic number and approximate graph coloring. (FOCS 2001, invited to JCSS)
Query efficient PCPs with perfect completeness. With Johan Hastad (FOCS 2001)
Metric Embeddings
The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into L1. With Nisheeth Vishnoi (FOCS 2005, shared the Best Paper Award, invited to JACM).
Non-embeddability theorems via Fourier analysis. With Assaf Naor (FOCS 2005).
On earthmover distance, metric labeling, and 0-extension. With Howard Karloff, Aranyak Mehta and Yuval Rabani (STOC 2006).
Integrality gaps for sparsest cut and minimum linear arrangement problems. With Nikhil Devanur, Rishi Saket and Nisheeth Vishnoi (STOC 2006).
Lower Bounds
Cell-probe lower bounds for partial match problem. With T.S. Jayram, S. Ravi Kumar, Yuval Rabani (STOC 2003, invited to JCSS)
Near-optimal lower bounds on the multi-party communication complexity of set-disjointness. With Amit Chakrabarti, Xiaodong Sun (Complexity 2003)
Evasiveness of subgraph containment and related properties. With Amit Chakrabarti, Yaoyun Shi (In SICOMP, preliminary version in STACS 2001)
Improved lower bounds on the randomized complexity of graph properties. With Amit Chakrabarti (ICALP 2001)
Miscellaneous
Fitting algebraic curves to noisy data. With Sanjeev Arora (STOC 2002, invited to JCSS)
Parameterized complexity of finding hereditary properties. With Venkatesh Raman (COCOON 2000, invited to TCS)
Other Technical Writings
Monotone span programs. Junior Thesis, IIT Bombay, 1998. Advisor : Sundar Vishwanathan .
Set systems with restricted intersections. Senior Thesis, IIT Bombay, 1999. Advisor : Sundar Vishwanathan.
 Update your faculty profile
 Back to Top
|
