| Publication | Date of Publication | Type |
|---|
| Bounded geometries, fractals, and low-distortion embeddings | 2026-05-29 | Paper |
| Measured descent: a new embedding method for finite metrics | 2026-05-29 | Paper |
| Approximating edit distance efficiently | 2026-05-29 | Paper |
| Algorithms on negatively curved spaces | 2026-05-29 | Paper |
| A polylogarithmic approximation of the minimum bisection | 2026-05-08 | Paper |
| Sketching graphs and combinatorial optimization (invited talk) | 2026-03-18 | Paper |
| Cut sparsification and succinct representation of submodular hypergraphs | 2026-01-14 | Paper |
| Fully-scalable MPC algorithms for clustering in high dimension | 2026-01-14 | Paper |
| Moderate dimension reduction for k-center clustering | 2025-11-24 | Paper |
| Breaking the cubic barrier for all-pairs max-flow: Gomory-Hu tree in nearly quadratic time | 2025-08-15 | Paper |
| Gap edit distance via non-adaptive queries: simple and optimal | 2025-08-15 | Paper |
| The power of uniform sampling for coresets | 2025-08-15 | Paper |
| Streaming facility location in high dimension via geometric hashing | 2025-08-15 | Paper |
| Spectral hypergraph sparsifiers of nearly linear size | 2025-08-13 | Paper |
| APMF < APSP? Gomory-Hu tree for unweighted graphs in almost-quadratic time | 2025-08-13 | Paper |
| Cut-equivalent trees are optimal for min-cut queries | 2025-08-12 | Paper |
| Sublinear algorithms for gap edit distance | 2025-08-12 | Paper |
| Spectral approaches to nearest neighbor search | 2025-08-05 | Paper |
| Everywhere-sparse spanners via dense subgraphs | 2025-05-05 | Paper |
| Polylogarithmic approximation for edit distance and the asymmetric query complexity | 2025-04-29 | Paper |
Streaming algorithms for geometric Steiner forest
ACM Transactions on Algorithms | 2025-02-21 | Paper |
| Lower bounds for pseudo-deterministic counting in a stream | 2024-11-14 | Paper |
Coresets for kernel clustering
Machine Learning | 2024-10-03 | Paper |
| Clustering permutations: new techniques with streaming applications | 2024-09-25 | Paper |
| An algorithmic bridge between Hamming and Levenshtein distances | 2024-09-25 | Paper |
| Relaxed Voronoi: a simple framework for terminal-clustering problems | 2024-08-26 | Paper |
| Friendly cut sparsifiers and faster Gomory-Hu trees | 2024-07-19 | Paper |
| Streaming algorithms for geometric Steiner forest | 2024-06-24 | Paper |
| Exact flow sparsification requires unbounded size | 2024-05-14 | Paper |
| Streaming Euclidean \textsc{Max-Cut}: dimension vs data reduction | 2024-05-08 | Paper |
Labelings vs. embeddings: on distributed and prioritized representations of distances
Discrete & Computational Geometry | 2024-04-02 | Paper |
scientific article; zbMATH DE number 7799589 (Why is no real title available?)
(available as arXiv preprint) | 2024-02-05 | Paper |
scientific article; zbMATH DE number 7788386 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
Coresets for clustering in excluded-minor graphs and beyond
(available as arXiv preprint) | 2024-01-15 | Paper |
Comparison of matrix norm sparsification
Algorithmica | 2023-12-13 | Paper |
Almost-linear <i>ε</i> -emulators for planar graphs
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
Subcubic algorithms for Gomory–Hu tree in unweighted graphs
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Towards tight bounds for spectral sparsification of hypergraphs
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
| scientific article; zbMATH DE number 7650299 (Why is no real title available?) | 2023-02-03 | Paper |
Distributed sparse normal means estimation with sublinear communication
Information and Inference: A Journal of the IMA | 2022-10-24 | Paper |
Universal streaming of subset norms
Theory of Computing | 2022-10-18 | Paper |
Almost-smooth histograms and sliding-window graph algorithms
Algorithmica | 2022-10-06 | Paper |
Faster algorithms for all-pairs bounded min-cuts
(available as arXiv preprint) | 2022-07-21 | Paper |
scientific article; zbMATH DE number 7559046 (Why is no real title available?)
(available as arXiv preprint) | 2022-07-18 | Paper |
scientific article; zbMATH DE number 7559154 (Why is no real title available?)
(available as arXiv preprint) | 2022-07-18 | Paper |
Smoothness of Schatten norms and sliding-window matrix streams
Information Processing Letters | 2022-06-03 | Paper |
Faster algorithms for orienteering and \(k\)-TSP
Theoretical Computer Science | 2022-04-19 | Paper |
New algorithms and lower bounds for all-pairs max-flow in undirected graphs
Theory of Computing | 2021-10-25 | Paper |
Tight recovery guarantees for orthogonal matching pursuit under Gaussian noise
Information and Inference: A Journal of the IMA | 2021-10-13 | Paper |
Labelings vs. Embeddings: On Distributed Representations of Distances
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
Networks on which hot-potato routing does not livelock
Distributed Computing | 2020-12-03 | Paper |
scientific article; zbMATH DE number 7204472 (Why is no real title available?)
(available as arXiv preprint) | 2020-05-27 | Paper |
Refined vertex sparsifiers of planar graphs
SIAM Journal on Discrete Mathematics | 2020-01-10 | Paper |
Flow-Cut Gaps and Face Covers in Planar Graphs
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Towards \((1 + \varepsilon)\)-approximate flow sparsifiers
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Non-uniform graph partitioning
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Mimicking Networks and Succinct Representations of Terminal Cuts
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
| Partitioning graphs into balanced components | 2019-05-06 | Paper |
| How hard is it to approximate the best Nash equilibrium? | 2019-05-06 | Paper |
| scientific article; zbMATH DE number 7051256 (Why is no real title available?) | 2019-05-06 | Paper |
Conditional Lower Bounds for All-Pairs Max-Flow
ACM Transactions on Algorithms | 2019-03-28 | Paper |
Cheeger-type approximation for sparsest st-cut
ACM Transactions on Algorithms | 2018-11-05 | Paper |
Sketching and embedding are equivalent for norms
SIAM Journal on Computing | 2018-07-04 | Paper |
Local reconstruction of low-rank matrices and subspaces
Random Structures & Algorithms | 2017-12-13 | Paper |
Metric decompositions of path-separable graphs
Algorithmica | 2017-11-09 | Paper |
Efficient Regression in Metric Spaces via Approximate Lipschitz Extension
IEEE Transactions on Information Theory | 2017-10-19 | Paper |
| Color-distance oracles and snippets | 2017-10-17 | Paper |
| A nonlinear approach to dimension reduction | 2017-09-29 | Paper |
| Approximate nearest neighbor search in metrics of planar graphs | 2017-08-31 | Paper |
Towards resistance sparsifiers
(available as arXiv preprint) | 2017-08-31 | Paper |
Streaming symmetric norms via measure concentration
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Sparsification of two-variable valued constraint satisfaction problems
SIAM Journal on Discrete Mathematics | 2017-06-23 | Paper |
Sketching cuts in graphs and hypergraphs
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science | 2017-05-19 | Paper |
Efficient Classification for Metric Data
IEEE Transactions on Information Theory | 2017-05-16 | Paper |
Tight Bounds for Gomory-Hu-like Cut Counting
Graph-Theoretic Concepts in Computer Science | 2016-12-22 | Paper |
The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
SIAM Journal on Computing | 2016-09-02 | Paper |
The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
SIAM Journal on Computing | 2016-09-02 | Paper |
On sketching quadratic forms
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science | 2016-04-15 | Paper |
Adaptive metric dimensionality reduction
Theoretical Computer Science | 2016-02-26 | Paper |
A nonlinear approach to dimension reduction
Discrete & Computational Geometry | 2015-12-02 | Paper |
Fault-tolerant spanners
Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing | 2015-09-11 | Paper |
Sketching and embedding are equivalent for norms
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
| Approximate classification via earthmover metrics | 2015-08-03 | Paper |
| scientific article; zbMATH DE number 6469222 (Why is no real title available?) | 2015-08-03 | Paper |
Do semidefinite relaxations solve sparse PCA up to the information limit?
The Annals of Statistics | 2015-07-06 | Paper |
Do semidefinite relaxations solve sparse PCA up to the information limit?
The Annals of Statistics | 2015-07-06 | Paper |
Private approximation of NP-hard functions
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
Online server allocation in a server farm via benefit task systems
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
| Estimating the sortedness of a data stream | 2014-12-18 | Paper |
Vertex sparsifiers: new results from old techniques
SIAM Journal on Computing | 2014-11-14 | Paper |
Approximating the minimum bisection size (extended abstract)
Proceedings of the thirty-second annual ACM symposium on Theory of computing | 2014-09-26 | Paper |
The smoothed complexity of edit distance
ACM Transactions on Algorithms | 2014-09-09 | Paper |
Min-max Graph Partitioning and Small Set Expansion
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
Streaming algorithms via precision sampling
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
Min-Max Graph Partitioning and Small Set Expansion
SIAM Journal on Computing | 2014-07-30 | Paper |
Min-Max Graph Partitioning and Small Set Expansion
SIAM Journal on Computing | 2014-07-30 | Paper |
Orienting fully dynamic graphs with worst-case time bounds
Automata, Languages, and Programming | 2014-07-01 | Paper |
Preserving terminal distances using minors
SIAM Journal on Discrete Mathematics | 2014-06-19 | Paper |
Directed spanners via flow-based linear programs
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
Directed spanners via flow-based linear programs
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
Proximity algorithms for nearly doubling spaces
SIAM Journal on Discrete Mathematics | 2014-04-10 | Paper |
Multiply balanced k-partitioning
LATIN 2014: Theoretical Informatics | 2014-03-31 | Paper |
Adaptive Metric Dimensionality Reduction
Lecture Notes in Computer Science | 2013-11-06 | Paper |
Preserving terminal distances using minors
Lecture Notes in Computer Science | 2013-08-12 | Paper |
Embedding the Ulam metric into \(\ell_{1}\)
Theory of Computing | 2011-05-24 | Paper |
Metric clustering via consistent labeling
Theory of Computing | 2011-05-24 | Paper |
How Hard Is It to Approximate the Best Nash Equilibrium?
SIAM Journal on Computing | 2011-05-17 | Paper |
Pricing commodities
Theoretical Computer Science | 2011-02-21 | Paper |
The computational hardness of estimating edit distance
SIAM Journal on Computing | 2011-01-17 | Paper |
Polylogarithmic approximation for edit distance and the asymmetric query complexity
Property Testing | 2010-10-12 | Paper |
Approximating sparsest cut in graphs of bounded treewidth
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2010-09-10 | Paper |
Proximity algorithms for nearly-doubling spaces
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2010-09-10 | Paper |
Vertex Sparsifiers: New Results from Old Techniques
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2010-09-10 | Paper |
Polylogarithmic inapproximability
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Improved lower bounds for embeddings into <i>L</i><sub>1</sub>
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
The intrinsic dimensionality of graphs
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
| scientific article; zbMATH DE number 5764821 (Why is no real title available?) | 2010-08-06 | Paper |
| scientific article; zbMATH DE number 5764809 (Why is no real title available?) | 2010-08-06 | Paper |
Improved lower bounds for embeddings into \(L_1\)
SIAM Journal on Computing | 2010-01-06 | Paper |
Asymmetric <i>k</i> -center is log <sup>*</sup> <i>n</i> -hard to approximate
Journal of the ACM | 2008-12-21 | Paper |
The intrinsic dimensionality of graphs
Combinatorica | 2008-10-22 | Paper |
The Smoothed Complexity of Edit Distance
Automata, Languages and Programming | 2008-08-28 | Paper |
Pricing Commodities, or How to Sell When Buyers Have Restricted Valuations
Approximation and Online Algorithms | 2008-02-20 | Paper |
On the hardness of approximating Multicut and Sparsest-Cut
Computational Complexity | 2007-11-05 | Paper |
Integrality Ratio for Group Steiner Trees and Directed Steiner Trees
SIAM Journal on Computing | 2007-10-22 | Paper |
A Polylogarithmic Approximation of the Minimum Bisection
SIAM Review | 2006-06-01 | Paper |
The black-box complexity of nearest-neighbor search
Theoretical Computer Science | 2006-01-09 | Paper |
Measured descent: A new embedding method for finite metrics
Geometric and Functional Analysis. GAFA | 2005-11-14 | Paper |
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Lecture Notes in Computer Science | 2005-08-25 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2005-08-24 | Paper |
Hardness of Approximation for Vertex-Connectivity Network Design Problems
SIAM Journal on Computing | 2005-02-21 | Paper |
Metric embeddings -- beyond one-dimensional distortion
Discrete & Computational Geometry | 2004-12-16 | Paper |
| scientific article; zbMATH DE number 2079317 (Why is no real title available?) | 2004-07-28 | Paper |
| scientific article; zbMATH DE number 2079350 (Why is no real title available?) | 2004-07-28 | Paper |
| scientific article; zbMATH DE number 1947057 (Why is no real title available?) | 2003-07-07 | Paper |
The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
SIAM Journal on Computing | 2003-06-19 | Paper |
On cutting a few vertices from a graph
Discrete Applied Mathematics | 2003-06-10 | Paper |
A polylogarithmic approximation of the minimum bisection
SIAM Journal on Computing | 2002-04-23 | Paper |
| On approximating the achromatic number (preliminary version) | 2002-03-14 | Paper |
On approximating the achromatic number
SIAM Journal on Discrete Mathematics | 2001-11-11 | Paper |
| Finding and certifying a large hidden clique in a semirandom graph | 2000-07-13 | Paper |
| scientific article; zbMATH DE number 1445353 (Why is no real title available?) | 2000-05-10 | Paper |
