2023
Reliable Spanners for Metric Spaces.
ACM Trans. Algorithms, January, 2023
2019
A Simple Proof of the Johnson-Lindenstrauss Extension Theorem.
Am. Math. Mon., 2019
2016
Encyclopedia of Algorithms, 2016
2015
A node-capacitated Okamura-Seymour theorem.
Math. Program., 2015
2014
Expanders with respect to Hadamard spaces and random graphs: extended abstract.
Proceedings of the Innovations in Theoretical Computer Science, 2014
2013
Expanders with respect to Hadamard spaces and random graphs.
CoRR, 2013
2010
Maximum gradient embeddings and monotone clustering.
Comb., 2010
Towards a Calculus for Non-Linear Spectral Gaps.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010
2009
Fast C-K-R Partitions of Sparse Graphs.
Chic. J. Theor. Comput. Sci., 2009
2008
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008
C-K-R Partitions of Sparse Graphs
CoRR, 2008
Markov convexity and local rigidity of distorted metrics.
Proceedings of the 24th ACM Symposium on Computational Geometry, 2008
2006
Fast Construction of Nets in Low-Dimensional Metrics and Their Applications.
SIAM J. Comput., 2006
Ramsey-type theorems for metric spaces with applications to online problems.
J. Comput. Syst. Sci., 2006
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006
Ramsey partitions and proximity data structures.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006
2005
Randomized k-server algorithms for growth-rate bounded graphs.
J. Algorithms, 2005
Metric structures in <i>L</i><sub>1</sub>: dimension, snowflakes, and average distortion.
Eur. J. Comb., 2005
Some Low Distortion Metric Ramsey Problems.
Discret. Comput. Geom., 2005
2004
Online companion caching.
Theor. Comput. Sci., 2004
Multiembedding of Metric Spaces.
SIAM J. Comput., 2004
Low dimensional embeddings of ultrametrics.
Eur. J. Comb., 2004
Multi-Embedding of Metric Spaces
CoRR, 2004
Randomized <i>k</i>-server algorithms for growth-rate bounded graphs.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004
Dimension reduction for ultrametrics.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004
Metric Structures in L1: Dimension, Snowflakes, and Average Distortion.
Proceedings of the LATIN 2004: Theoretical Informatics, 2004
Measured Descent: A New Embedding Method for Finite Metrics.
Proceedings of the 45th Symposium on Foundations of Computer Science, 2004
2003
Better Algorithms for Unfair Metrical Task Systems and Applications.
SIAM J. Comput., 2003
On metric ramsey-type phenomena.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003
Multi-embedding and path approximation of metric spaces.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003
2002
Online Companion Caching.
Proceedings of the Algorithms, 2002
2001
A Ramsy-type Theorem for Metric Spaces and its Applications for Metrical Task Systems and Related Problems.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001
1997
Truly Online Paging with Locality of Reference.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997