Topics
Approximation:
SDP
Approximation:
Clustering
Approximation:
Network Design
Approximation: TSP and
Routing
Other Approximation
Sketching, Streaming
and Similarity Search
Finite
Metrics
Online Algorithms
Other Publications


Recent Papers
 Online Bipartite Matching with Decomposable Weights
with Monika Henzinger and Huy Le Nguyen,
in Proceedings of the 22nd European Symposium on Algorithms (2014).
 Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability
with Aditya Bhaskara and Aravindan Vijayaraghavan,
in Proceedings of the 27th Annual Conference on Learning Theory (2014).
 Smoothed Analysis of Tensor Decompositions
with Aditya Bhaskara, Ankur Moitra and Aravindan Vijayaraghavan,
in Proceedings of the 46th ACM Symposium on Theory of Computing (2014).
 Multireference Alignment using Semidefinite Programming
with Afonso Bandeira, Amit Singer and Andy Zhu,
in Proceedings of the 5th Innovations in Theoretical Computer Science (2014).
 Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach
with Nikhil Bansal, Ravishankar Krishnaswamy and Shi Li,
in Proceedings of the 25th Annual ACMSIAM Symposium on Discrete Algorithms (2014).
 A Dependent LProunding Approach for the kMedian Problem
with Shi Li,
in Proceedings of the 39th International Colloquium on Automata, Languages and Programming (2012).
 On Quadratic Programming with a Ratio Objective
with Aditya Bhaskara, Rajsekar Manokaran and Aravindan Vijayaraghavan,
in Proceedings of the 39th International Colloquium on Automata, Languages and Programming (2012).
 Highconfidence nearduplicate image detection
with Wei Dong, Zhe Wang and Kai Li,
in Proceedings of the International Conference on Multimedia Retrieval (2012).
 Polynomial integrality gaps for strong SDP relaxations of Densest ksubgraph
with Aditya Bhaskara, Venkatesan Guruswami, Aravindan Vijayaraghavan and Yuan Zhou,
in Proceedings of the 23nd Annual ACMSIAM Symposium on Discrete Algorithms (2012).
 Efficient knearest neighbor graph construction for generic similarity measures
with Wei Dong and Kai Li,
in Proceedings of the 20th International Conference on World Wide Web WWW (2011).
 Near Linear Lower Bound for Dimension Reduction in L1
with Alexandr Andoni, Ofer Neiman and Huy L. Nguyen,
in Proceedings of the 52nd Annual IEEE Conference on Foundations of Computer Science (2011).
 Tight Hardness Results for Minimizing Discrepancy
with Alantha Newman and Aleksander Nikolov,
in Proceedings of the 22nd Annual ACMSIAM Symposium on Discrete Algorithms (2011).
 Vertex Sparsifiers and Abstract Rounding Algorithms
with Tom Leighton, Shi Li and Ankur Moitra,
in Proceedings of the 51st Annual IEEE Conference on Foundations of Computer Science (2010).
 Detecting high logdensities: an O(n^{1/4}) approximation for densest ksubgraph
with Aditya Bhaskara, Eden Chlamtac, Uri Feige and Aravindan Vijayaraghavan,
in Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (2010).
 Improved Approximation Algorithms for Label Cover Problems
with MohammadTaghi Hajiaghayi and Howard Karloff,
in Proceedings of the 17th Annual European Symposium on Algorithms (ESA) (2009).
 Every Permutation CSP of arity 3 is Approximation Resistant
with Venkat Guruswami and Rajsekar Manokaran,
in Proceedings of the 24th IEEE Conference on Computational Complexity (CCC) (2009).
 Integrality Gaps for SheraliAdams Relaxations
with Konstantin Makarychev and Yury Makarychev,
in Proceedings of the 41st Annual ACM Symposium on Theory of Computing (2009).
 MaxMin Allocation via Degree LowerBounded Arborescences
with MohammadHossein Bateni and Venkat Guruswami,
in Proceedings of the 41st Annual ACM Symposium on Theory of Computing (2009).
 Efficiently matching sets of features with random histograms
with Wei Dong, Zhe Wang and Kai Li,
in Proceedings of the 16th International ACM Conference on Multimedia (2008).
 Modeling LSH for performance tuning
with Wei Dong, Zhe Wang, William Josephson and Kai Li,
in Proceedings of the 17th ACM Conference on Information and Knowledge Management (CIKM) (2008).
 Asymmetric distance estimation with sketches for similarity search in highdimensional spaces
with Wei Dong and Kai Li,
in Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (2008).
 Online multicast with egalitarian cost sharing
with Howard Karloff, Claire Mathieu, Joseph (Seffi) Naor and Mike Saks,
in Proceedings of the 20th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA) (2008).
 Local Global Tradeoffs in Metric Embeddings
with Konstantin Makarychev and Yury Makarychev,
in Proceedings of the 48th Annual IEEE Conference on Foundations of Computer Science (2007).
 On the Advantage over Random for Maximum Acyclic Subgraph
with Konstantin Makarychev and Yury Makarychev,
in Proceedings of the 48th Annual IEEE Conference on Foundations of Computer Science (2007).
 MultiProbe LSH: Efficient Indexing for HighDimensional Similarity Search
with Qin Lv, William Josephson, Zhe Wang and Kai Li,
in Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB) (2007).
 Sizing sketches: a rankbased analysis for similarity search
with Zhe Wang, Wei Dong, William Josephson, Qin Lv, and Kai Li,
ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (2007).
 Improved approximation for directed cut problems
with Amit Agarwal and Noga Alon,
in Proceedings of the 39th Annual ACM Symposium on Theory of Computing (2007).
 NearOptimal Algorithms for Maximum Constraint Satisfaction Problems
with Konstantin Makarychev and Yury Makarychev,
in Proceedings of the 18th Annual ACMSIAM Symposium on Discrete Algorithms (2007).
 A Divide and Conquer Algorithm for dDimensional Arrangement
with Konstantin Makarychev and Yury Makarychev,
in Proceedings of the 18th Annual ACMSIAM Symposium on Discrete Algorithms (2007).
 NearOptimal
Algorithms for Unique Games
with Konstantin Makarychev and Yury Makarychev,
in Proceedings of
the 38th ACM Symposium on Theory of Computing (2006).
 New
Approximation Guarantees for Chromatic Number
with Sanjeev Arora and Eden Chlamtac,
in Proceedings of the 38th ACM
Symposium on Theory of Computing (2006).
 Ferret:
A Toolkit for ContentBased Similarity Search
with Christine Lv, William
Josephson, Zhe Wang and Kai Li,
to
appear in Proceedings of ACM SIGOS EuroSys Conference (2006).
 l_{2}^{2}
spreading metrics for vertex ordering problems
with MohammadTaghi
Hajiaghayi, Howard Karloff and Satish Rao
in Proceedings of the 17th
ACMSIAM Symposium on Discrete
Algorithms (2006).
 Directed
Metrics and Directed Graph Partitioning Problems
with Konstantin Makarychev and Yury Makarychev
in Proceedings of the 17th
ACMSIAM Symposium on Discrete
Algorithms (2006).
 A
Robust Maximum Completion Time Measure for Scheduling
with Samir Khuller,
in Proceedings of the 17th
ACMSIAM Symposium on Discrete
Algorithms (2006).
 Fitting
tree metrics: Hierarchical Clustering and Phylogeny
with Nir Ailon,
in Proceedings of the 46th Annual IEEE Symposium on Foundations of
Computer Science (2005).
 Sampling
Bounds for Stochastic Optimization
with
Chandra Chekuri and
Martin Pal,
in Proceedings of APPROXRANDOM (2005).
 O(sqrt{log
n}) approximation algorithms for Min UnCut, Min 2CNF Deletion, and
directed cut problems
with Amit Agarwal, Konstantin Makarychev, Yury
Makarychev,
in Proceedings of the 37th ACM Symposium on Theory of
Computing (2005).
 Aggregating
Inconsistent Information: Ranking and Clustering
with Nir Ailon and Alantha Newman,
in Proceedings of the 37th ACM Symposium on Theory of
Computing (2005).
 On
Nonuniform Multicommodity BuyatBulk Network Design
with Adriana Karagiozova,
in Proceedings of the 37th ACM Symposium on Theory of
Computing (2005).
Approximation
Algorithms: Semidefinite Programming
 NearOptimal
Algorithms for Unique Games
with Konstantin Makarychev and Yury Makarychev,
in Proceedings of
the 38th ACM Symposium on Theory of Computing (2006).
 New
Approximation Guarantees for Chromatic Number
with Sanjeev Arora and Eden Chlamtac,
in Proceedings of the 38th ACM
Symposium on Theory of Computing (2006).
 l_{2}^{2}
spreading metrics for vertex ordering problems
with MohammadTaghi
Hajiaghayi, Howard Karloff and Satish Rao
in Proceedings of the 17th
ACMSIAM Symposium on Discrete
Algorithms (2006).
 O(sqrt{log
n}) approximation algorithms for Min UnCut, Min 2CNF Deletion, and
directed cut problems
with Amit Agarwal, Konstantin Makarychev, Yury
Makarychev,
in Proceedings of the 37th ACM Symposium on Theory of
Computing (2005).
 Maximizing quadratic programs: extending
Grothendieck's inequality
with Anthony Wirth,
in Proceedings of the 45th Annual IEEE Symposium on
Foundations of Computer Science (2004).
 On
Semidefinite Programming Relaxations for Graph Coloring and Vertex
Cover,
in Proceedings of the 13th Annual ACMSIAM Symposium on
Discrete Algorithms, (2002).
Approximation
Algorithms: Clustering Problems
 Aggregating
Inconsistent Information: Ranking and Clustering
with Nir Ailon and Alantha Newman,
in Proceedings of the 37th ACM Symposium on Theory of
Computing (2005).
 Clustering
with Qualitative Information,
with V. Guruswami and A. Wirth,
in Proceedings of the 44th Annual IEEE Symposium on
Foundations of Computer Science (2003).
 Clustering
to Minimize the Sum of Cluster Diameters,
with R. Panigrahy,
in Proceedings of the 33rd Annual ACM Symposium on Theory
of Computing, (2001).
 Approximating
MinSum kClustering in Metric Spaces,
with Y. Bartal and D. Raz,
in Proceedings of the 33rd Annual ACM Symposium on Theory
of Computing, (2001).
 Algorithms
for Facility Location with Outliers,
with S. Khuller, D. Mount and G. Narasimhan,
in Proceedings of the 12th Annual ACMSIAM Symposium on
Discrete Algorithms, (2001).
 Improved
Combinatorial Algorithms for the Facility Location and kMedian
Problems
with S. Guha,
in Proceedings of the 40th Annual IEEE Conference on
Foundations of Computer Science (1999), extended version
 A Constant
Factor Approximation Algorithm for the kMedian Problem
with S. Guha, E. Tardos and D. Shmoys,
in Proceedings of the 31st Annual ACM Symposium on Theory
of Computing (1999),
invited to special issue of JCSS for STOC '99.
Approximation
Algorithms: Network Design
 On
Nonuniform Multicommodity BuyatBulk Network Design
with Adriana Karagiozova,
in Proceedings of the 37th ACM Symposium on Theory of
Computing (2005).
 On the
Advantage of Network Coding for Improving Network Throughput
with Amit Agarwal,
in Proceedings of the IEEE Information Theory Workshop
(2004).
 Resource
Optimization in QoS Multicast Routing of RealTime Multimedia
with J. Naor and B. Schieber,
in Proceedings of the 19th Annual IEEE INFOCOM (2000).
 Approximating
Wire Length in Zero and Bounded Skew Clock Trees
with J. Kleinberg, S. Rajagopalan, S. Ravikumar, A. Sahai and A.
Tomkins,
in Proceedings of the 10th Annual ACMSIAM Symposium on
Discrete Algorithms (1999), extended version.
 Rounding
Via Trees: Deterministic Approximation Algorithms for Group Steiner
Trees and kMedian,
with C. Chekuri, A. Goel and S. Guha,
in Proceedings of the 30th Annual ACM Symposium on
Theory
of Computing (1998).
 Approximation
Algorithms for Directed Steiner Tree Problems,
with C. Chekuri, T. Cheung, Z. Dai, A. Goel, S. Guha and M. Li,
in Journal of Algorithms, vol. 33, pp. 7391 (1999), preliminary
version in Proceedings of the 9th Annual ACMSIAM Symposium on
Discrete Algorithms (1998).
Approximation
Algorithms: TSP and Routing
Other Approximation Algorithms
 A
Robust Maximum Completion Time Measure for Scheduling
with Samir Khuller,
in Proceedings of the 17th
ACMSIAM Symposium on Discrete
Algorithms (2006).
 Sampling
Bounds for Stochastic Optimization
with
Chandra Chekuri and
Martin Pal,
in Proceedings of APPROXRANDOM (2005).
 Approximation
the Average Response Time in Broadcast Scheduling
with Nikhil Bansal, Sanjeev Khanna and Seffi Naor,
in Proceedings of the 16th ACMSIAM Symposium on
Discrete
Algorithms (2005).
 Approximating
The Smallest Grammar: Kolmogorov Complexity in Natural Models,
with E. Lehman, D. Liu, R. Panigrahy, M. Prabhakaran, A. Rasala, A.
Sahai, and A. Shelat,
in Proceedings of the 34th Annual ACM Symposium on
Theory
of Computing, (2002).
 Combinatorial
Feature Selection Problems,
with V. Guruswami, S. Rajagopalan, S. Ravikumar and A. Sahai,
in Proceedings of the 41st Annual IEEE Conference on
Foundations of Computer Science, (2000).
 Greedy
Approximation Algorithms for Finding Dense Components in Graphs,
in Proceedings of APPROX, (2000).
 Constrained
TSP and Low Power Computing,
with C. Silverstein, R. Motwani and P. Raghavan,
in Proceedings of Workshop on Algorithms and Data
Structures (WADS), (1997).
Sketching, Streaming and
Similarity Search
 Ferret:
A Toolkit for ContentBased Similarity Search
with Christine Lv,
William
Josephson, Zhe Wang and Kai Li,
to
appear in Proceedings of ACM SIGOS EuroSys Conference (2006).
 Image
Similarity Search with Compact Data Structures
with Qin Lv and Kai Li,
in Proceedings of the ACM Conference on Information and
Knowledge Management (CIKM 2004).
 Better
Streaming Algorithms for Clustering Problems,
with L. O'Callaghan and R. Panigrahy,
in Proceedings of the 35th Annual ACM Symposium on Theory of
Computing, (2003).
 Finding
Frequent Items in Data Streams,
with K. Chen and M. FarachColton,
in Proceedings of the 29th International Colloquium on
Automata Languages and Programming, (2002).
 New
Algorithms for Subset Query, Partial Match, Orthogonal Range Searching
and Related Problems,
with P. Indyk and R. Panigrahy,
in Proceedings of the 29th International Colloquium on
Automata Languages and Programming, (2002).
 Similarity
Estimation Techniques from Rounding Algorithms,
in Proceedings of the 34th Annual ACM Symposium on
Theory
of Computing, (2002).
 MinWise
Independent Permutations,
with A. Broder, A. Frieze and M. Mitzenmacher,
in Journal of Computer Systems and Sciences, vol. 60(3), pp. 630659
(2000) (special issue for STOC '98), preliminary version in
Proceedings of the 30th Annual ACM Symposium on Theory of Computing
(1998),
Finite
Metrics
 Directed
Metrics and Directed Graph Partitioning Problems
with Konstantin Makarychev and Yury Makarychev
in Proceedings of the 17th
ACMSIAM Symposium on Discrete
Algorithms (2006).
 Fitting
tree metrics: Hierarchical Clustering and Phylogeny
with Nir Ailon,
in Proceedings of the 46th Annual IEEE Symposium on Foundations of
Computer Science (2005).
 A
Tight Threshold for Metric Ramsey Phenomena
with Adriana Karagiozova,
in Proceedings of the 16th ACMSIAM Symposium on
Discrete
Algorithms (2005).
 On
the Impossibility of Dimension Reduction in l_{1
}with B. Brinkman,
in Proceedings of the 44th Annual IEEE Symposium on Foundations of
Computer Science (2003), best paper award.
 Dimension
Reduction in the l_{1} norm,
with A. Sahai,
in Proceedings of the 43rd Annual IEEE Conference on
Foundations of Computer Science (2002).
 Approximating
a Finite Metric by a Small Number of Tree Metrics,
with C. Chekuri, A. Goel, S. Guha and S. Plotkin,
in Proceedings of the 39th Annual IEEE Conference on
Foundations of Computer Science (1998).
Online
Algorithms
 Query
Strategies for Priced Information,
with R. Fagin, V. Guruswami, J. Kleinberg, P. Raghavan and A. Sahai,
in Proceedings of the 32nd Annual ACM Symposium on
Theory
of Computing (2000), to appear in special issue of JCSS for STOC
2000.
 Delayed
Information and Action in OnLine Algorithms,
with S. Albers and M. Mitzenmacher,
in Information and Computation, vol 170, pp. 135152 (2001), preliminary
version in Proceedings of the 39th Annual IEEE Conference on
Foundations of Computer Science (1998).
 The
Dynamic Servers Problem,
with D. Halperin and R. Motwani,
in Proceedings of the 9th Annual ACMSIAM Symposium on
Discrete Algorithms (1998).
 Online
Load Balancing for Related Machines,
with P. Berman and M. Karpinski,
in Journal of Algorithms, vol. 35(1), pp. 108121, (2000), preliminary
version in Proceedings of Workshop on Algorithms and Data
Structures (WADS), (1997).
 Incremental Clustering and Dynamic
Information Retrieval,
with C. Chekuri, T. Feder and R. Motwani,
in Proceedings of the 29th Annual ACM Symposium on
Theory
of Computing (1997).
 On
Page
Migration and Other Relaxed Task Systems,
with Y. Bartal and P. Indyk,
in Theoretical Computer Science, vol. 268(1), pp. 4366 (2001),
preliminary version in Proceedings of the 8th Annual ACMSIAM Symposium
on Discrete Algorithms (1997).
Other
Publications
 Minimum Outage Transmission
over Fading Channels with Delay Constraint,
with R. Negi and J. Cioffi,
in Proceedings of the IEEE International Conference on
Communication, (2000).
 On
Targeting Markov Segments,
with P. Raghavan, S. Rajagopalan, S. Ravikumar, and A. Tomkins,
in Proceedings of the 31st Annual ACM Symposium on
Theory
of Computing (1999).
 A
Derandomization Using MinWise Independent Permutations,
with A. Broder and M. Mitzenmacher,
in Proceedings of the 2nd International Workshop on
Randomization and Approximation Techniques in Computer Science (1998).
