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