Please email me if you are interested in any of the papers I haven't yet uploaded. The classification of papers below into different areas is approximate.

Talks / Surveys

ü  Inapproximability of NP-complete problems, Discrete Fourier Analysis, and Geometry  (To appear in Proc. ICM 2010).

ü  On the Unique Games Conjecture  (Proc. CCC 2010).   Powerpoint slides.

ü  FOCS’05 Tutorial.

 

PCPs and Hardness of Approximation

ü  Inapproximability of hypergraph vertex cover and applications to scheduling problems.  With Nikhil Bansal  (Submitted).

ü  Inapproximability of  vertex cover and independent set in bounded degree graphs.  With Per Austrin and Muli Safra  (Complexity 2009). 

ü  SDP gaps and UGC-hardness for MaxCutGain.   With Ryan O'Donnell (FOCS 2006).

ü  A 3-query non-adaptive PCP with perfect completeness.   With Rishi Saket. (Complexity 2006)

ü  Better inapproximability results for maxclique, chromatic number and min-3Lin-deletion.   With Ashok Kumar Ponnuswami (ICALP 2006)

ü  Hardness of approximating the closest vector problem with pre-processing.   With Misha Alekhnovich, Guy Kindler, Nisheeth Vishnoi (FOCS 2005).

ü  Hardness of Max 3SAT with no mixed clauses.   With Venkatesan Guruswami (Complexity 2005).

ü  Inapproximability results for combinatorial auctions with submodular utility functions.   With Richard J. Lipton, Evangelos Markakis, Aranyak Mehta (WINE 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)

ü  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

ü  SDP  integrality gaps with local  L1-embeddability.     With Rishi Saket (FOCS 2009). 

ü  Hardness of embedding metric spaces of equal size.   With Rishi Saket (APPROX 2007).

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

ü  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 and accepted to JACM).

ü  Non-embeddability theorems via Fourier analysis.   With A.  Naor  (FOCS 2005).

Learning Theory

ü  Hardness of minimizing and learning DNF expressions.   With Rishi Saket   (FOCS 2008) .

ü  On hardness of learning intersection of two halfspaces.   With Rishi Saket   (STOC 2008) .

ü  Minimizing wide range regret with time selection functions.  With Ashok Kumar Ponnuswami.  (COLT 2008). 

ü  Hardness of reconstructing multivariate polynomials over finite fields.   With Parikshit Gopalan and Rishi Saket  (FOCS 2007, invited to SICOMP)

ü  New results for learning noisy parities and halfspaces.   With Vitaly Feldman, Parikshit Gopalan and Ashok Kumar Ponnuswami   (FOCS 2006, invited to  SICOMP)

Algorithmic Results

ü  Sharp kernel clustering algorithms and their associated Grothendieck inequalities.    With A. Naor.  (SODA 2010). 

ü  Approximate kernel clustering.  With A. Naor (FOCS 2008).

ü  Unique games on expanding constraint graphs are easy.   With Sanjeev Arora, Alexandra Kolla, David Steurer, Madhur Tulsiani, Nisheeth K. Vishnoi   (STOC 2008)

ü  Approximation algorithms for the max-min allocation problem.   With Ashok Kumar Ponnuswami.  (APPROX 2007)

ü  Linear equations modulo 2 and the L_1 diameter of convex bodies.   With A. Naor  (FOCS 2007)

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