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. |