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
ü
Hardness of
Approximation (ICM 2014). Video of talk available here
ü
Inapproximability of NP-complete problems, Discrete Fourier
Analysis, and Geometry (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 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. |