| Publication | Date of Publication | Type |
|---|
| Lower bounds for pseudo-deterministic counting in a stream | 2024-11-14 | Paper |
| Coresets for kernel clustering | 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 | 2024-04-02 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6187024 | 2024-02-05 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6147298 | 2024-01-15 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6147417 | 2024-01-15 | Paper |
| Comparison of matrix norm sparsification | 2023-12-13 | Paper |
| Almost-linear ε -emulators for planar graphs | 2023-12-08 | Paper |
| Subcubic algorithms for Gomory–Hu tree in unweighted graphs | 2023-11-14 | Paper |
| Towards tight bounds for spectral sparsification of hypergraphs | 2023-11-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5875634 | 2023-02-03 | Paper |
| Distributed sparse normal means estimation with sublinear communication | 2022-10-24 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5040832 | 2022-10-18 | Paper |
| Almost-smooth histograms and sliding-window graph algorithms | 2022-10-06 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5091155 | 2022-07-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5090373 | 2022-07-18 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5090495 | 2022-07-18 | Paper |
| Smoothness of Schatten norms and sliding-window matrix streams | 2022-06-03 | Paper |
| Faster algorithms for orienteering and \(k\)-TSP | 2022-04-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5158499 | 2021-10-25 | Paper |
| Tight recovery guarantees for orthogonal matching pursuit under Gaussian noise | 2021-10-13 | Paper |
| Labelings vs. Embeddings: On Distributed Representations of Distances | 2021-02-02 | Paper |
| New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs | 2021-02-02 | Paper |
| Networks on which hot-potato routing does not livelock | 2020-12-03 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5111350 | 2020-05-27 | Paper |
| Refined Vertex Sparsifiers of Planar Graphs | 2020-01-10 | Paper |
| Flow-Cut Gaps and Face Covers in Planar Graphs | 2019-10-15 | Paper |
| Towards (1 + ∊)-Approximate Flow Sparsifiers | 2019-06-20 | Paper |
| Non-Uniform Graph Partitioning | 2019-06-20 | Paper |
| Mimicking Networks and Succinct Representations of Terminal Cuts | 2019-05-15 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4633907 | 2019-05-06 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4633884 | 2019-05-06 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4633899 | 2019-05-06 | Paper |
| Conditional Lower Bounds for All-Pairs Max-Flow | 2019-03-28 | Paper |
| Cheeger-Type Approximation for Sparsest st -Cut | 2018-11-05 | Paper |
| Sketching and Embedding are Equivalent for Norms | 2018-07-04 | Paper |
| Local reconstruction of low‐rank matrices and subspaces | 2017-12-13 | Paper |
| Metric decompositions of path-separable graphs | 2017-11-09 | Paper |
| Efficient Regression in Metric Spaces via Approximate Lipschitz Extension | 2017-10-19 | Paper |
| Color-Distance Oracles and Snippets | 2017-10-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5365088 | 2017-09-29 | Paper |
| Approximate Nearest Neighbor Search in Metrics of Planar Graphs | 2017-08-31 | Paper |
| Towards Resistance Sparsifiers | 2017-08-31 | Paper |
| Streaming symmetric norms via measure concentration | 2017-08-17 | Paper |
| Sparsification of Two-Variable Valued Constraint Satisfaction Problems | 2017-06-23 | Paper |
| Sketching Cuts in Graphs and Hypergraphs | 2017-05-19 | Paper |
| Efficient Classification for Metric Data | 2017-05-16 | Paper |
| Tight Bounds for Gomory-Hu-like Cut Counting | 2016-12-22 | Paper |
| The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme | 2016-09-02 | Paper |
| On sketching quadratic forms | 2016-04-15 | Paper |
| Adaptive metric dimensionality reduction | 2016-02-26 | Paper |
| A nonlinear approach to dimension reduction | 2015-12-02 | Paper |
| Fault-tolerant spanners | 2015-09-11 | Paper |
| Sketching and Embedding are Equivalent for Norms | 2015-08-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5501372 | 2015-08-03 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5501341 | 2015-08-03 | Paper |
| Do semidefinite relaxations solve sparse PCA up to the information limit? | 2015-07-06 | Paper |
| Online server allocation in a server farm via benefit task systems | 2015-02-27 | Paper |
| Private approximation of NP-hard functions | 2015-02-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2934610 | 2014-12-18 | Paper |
| Vertex sparsifiers: new results from old techniques | 2014-11-14 | Paper |
| Approximating the minimum bisection size (extended abstract) | 2014-09-26 | Paper |
| The smoothed complexity of edit distance | 2014-09-09 | Paper |
| Min-max Graph Partitioning and Small Set Expansion | 2014-07-30 | Paper |
| Streaming Algorithms via Precision Sampling | 2014-07-30 | Paper |
| Min-Max Graph Partitioning and Small Set Expansion | 2014-07-30 | Paper |
| Orienting Fully Dynamic Graphs with Worst-Case Time Bounds | 2014-07-01 | Paper |
| Preserving Terminal Distances Using Minors | 2014-06-19 | Paper |
| Directed spanners via flow-based linear programs | 2014-06-05 | Paper |
| The traveling salesman problem | 2014-05-13 | Paper |
| Proximity Algorithms for Nearly Doubling Spaces | 2014-04-10 | Paper |
| Multiply Balanced k −Partitioning | 2014-03-31 | Paper |
| Adaptive Metric Dimensionality Reduction | 2013-11-06 | Paper |
| Preserving Terminal Distances Using Minors | 2013-08-12 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3002773 | 2011-05-24 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3002830 | 2011-05-24 | Paper |
| How Hard Is It to Approximate the Best Nash Equilibrium? | 2011-05-17 | Paper |
| Pricing commodities | 2011-02-21 | Paper |
| The Computational Hardness of Estimating Edit Distance | 2011-01-17 | Paper |
| Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity | 2010-10-12 | Paper |
| Approximating Sparsest Cut in Graphs of Bounded Treewidth | 2010-09-10 | Paper |
| Proximity Algorithms for Nearly-Doubling Spaces | 2010-09-10 | Paper |
| Vertex Sparsifiers: New Results from Old Techniques | 2010-09-10 | Paper |
| Polylogarithmic inapproximability | 2010-08-16 | Paper |
| Improved lower bounds for embeddings into L1 | 2010-08-16 | Paper |
| The intrinsic dimensionality of graphs | 2010-08-16 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3579410 | 2010-08-06 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3579398 | 2010-08-06 | Paper |
| Improved Lower Bounds for Embeddings into $L_1$ | 2010-01-06 | Paper |
| Asymmetric k -center is log * n -hard to approximate | 2008-12-21 | Paper |
| The intrinsic dimensionality of graphs | 2008-10-22 | Paper |
| The Smoothed Complexity of Edit Distance | 2008-08-28 | Paper |
| Pricing Commodities, or How to Sell When Buyers Have Restricted Valuations | 2008-02-20 | Paper |
| On the hardness of approximating Multicut and Sparsest-Cut | 2007-11-05 | Paper |
| Integrality Ratio for Group Steiner Trees and Directed Steiner Trees | 2007-10-22 | Paper |
| A Polylogarithmic Approximation of the Minimum Bisection | 2006-06-01 | Paper |
| The black-box complexity of nearest-neighbor search | 2006-01-09 | Paper |
| Measured descent: A new embedding method for finite metrics | 2005-11-14 | Paper |
| Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2005-08-25 | Paper |
| Automata, Languages and Programming | 2005-08-24 | Paper |
| Hardness of Approximation for Vertex-Connectivity Network Design Problems | 2005-02-21 | Paper |
| Metric embeddings -- beyond one-dimensional distortion | 2004-12-16 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4471269 | 2004-07-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4471309 | 2004-07-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4411287 | 2003-07-07 | Paper |
| The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set | 2003-06-19 | Paper |
| On cutting a few vertices from a graph | 2003-06-10 | Paper |
| A polylogarithmic approximation of the minimum bisection | 2002-04-23 | Paper |
| On approximating the achromatic number (preliminary version) | 2002-03-14 | Paper |
| On approximating the achromatic number | 2001-11-11 | Paper |
| Finding and certifying a large hidden clique in a semirandom graph | 2000-07-13 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4952672 | 2000-05-10 | Paper |
