|
+
PDF
Chat
|
Lipschitz Decompositions of Finite $\ell_{p}$ Metrics
|
2025
|
Robert Krauthgamer
Nir Petruschka
|
|
+
PDF
Chat
|
Near-Optimal Dimension Reduction for Facility Location
|
2024
|
Lingxiao Huang
Shaofeng H. -C. Jiang
Robert Krauthgamer
Dongsheng Yue
|
|
+
PDF
Chat
|
Streaming Algorithms for Geometric Steiner Forest
|
2024
|
Artur Czumaj
Shaofeng H.-C. Jiang
Robert Krauthgamer
Pavel VeselĂ˝
|
|
+
|
Streaming Euclidean Max-Cut: Dimension vs Data Reduction
|
2023
|
Xiaoyu Chen
Shaofeng H.-C. Jiang
Robert Krauthgamer
|
|
+
PDF
Chat
|
Exact Flow Sparsification Requires Unbounded Size
|
2023
|
Robert Krauthgamer
Ron Mosenzon
|
|
+
|
Lower Bounds for Pseudo-Deterministic Counting in a Stream
|
2023
|
Vladimir Braverman
Robert Krauthgamer
Aditya Krishnan
Shay Sapir
|
|
+
|
Fully Scalable MPC Algorithms for Clustering in High Dimension
|
2023
|
Artur Czumaj
Guichen Gao
Shaofeng H. -C. Jiang
Robert Krauthgamer
Pavel VeselĂ˝
|
|
+
|
Cut Sparsification and Succinct Representation of Submodular Hypergraphs
|
2023
|
Yotam Kenneth
Robert Krauthgamer
|
|
+
|
Moderate Dimension Reduction for $k$-Center Clustering
|
2023
|
Shaofeng H. -C. Jiang
Robert Krauthgamer
Shay Sapir
|
|
+
PDF
Chat
|
Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal
|
2022
|
Elazar Goldenberg
Tomasz Kociumaka
Robert Krauthgamer
Barna Saha
|
|
+
PDF
Chat
|
Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time
|
2022
|
Amir Abboud
Robert Krauthgamer
Jason Li
Debmalya Panigrahi
Thatchaphol Saranurak
Ohad Trabelsi
|
|
+
PDF
Chat
|
Streaming Facility Location in High Dimension via Geometric Hashing
|
2022
|
Artur Czumaj
Shaofeng H.-C. Jiang
Robert Krauthgamer
Pavel VeselĂ˝
Mingwei Yang
|
|
+
PDF
Chat
|
The Power of Uniform Sampling for Coresets
|
2022
|
Vladimir Braverman
Vincent Cohen-Addad
H.-C. Shaofeng Jiang
Robert Krauthgamer
Chris Schwiegelshohn
Mads Bech Toftrup
Xuan Wu
|
|
+
PDF
Chat
|
Almost-Smooth Histograms and Sliding-Window Graph Algorithms
|
2022
|
Robert Krauthgamer
David Reitblat
|
|
+
|
Almost-linear <i>Îľ</i> -emulators for planar graphs
|
2022
|
Hsien-Chih Chang
Robert Krauthgamer
Zihan Tan
|
|
+
PDF
Chat
|
Smoothness of Schatten norms and sliding-window matrix streams
|
2022
|
Robert Krauthgamer
Shay Sapir
|
|
+
PDF
Chat
|
Spectral Hypergraph Sparsifiers of Nearly Linear Size
|
2022
|
Michael Kapralov
Robert Krauthgamer
Jakab Tardos
Yuichi Yoshida
|
|
+
PDF
Chat
|
Distributed sparse normal means estimation with sublinear communication
|
2022
|
Chen Amiraz
Robert Krauthgamer
Boaz Nadler
|
|
+
PDF
Chat
|
Friendly Cut Sparsifiers and Faster Gomory-Hu Trees
|
2022
|
Amir Abboud
Robert Krauthgamer
Ohad Trabelsi
|
|
+
|
Comparison of Matrix Norm Sparsification
|
2022
|
Robert Krauthgamer
Shay Sapir
|
|
+
|
Near-Linear $\varepsilon$-Emulators for Planar Graphs
|
2022
|
Hsien-Chih Chang
Robert Krauthgamer
Zihan Tan
|
|
+
|
Optimal Vertex-Cut Sparsification of Quasi-Bipartite Graphs
|
2022
|
Itai Boneh
Robert Krauthgamer
|
|
+
|
Exact Flow Sparsification Requires Unbounded Size
|
2022
|
Robert Krauthgamer
Ron Mosenzon
|
|
+
|
Streaming Facility Location in High Dimension via Geometric Hashing
|
2022
|
Artur Czumaj
Shaofeng H. -C. Jiang
Robert Krauthgamer
Pavel VeselĂ˝
Mingwei Yang
|
|
+
|
The Power of Uniform Sampling for Coresets
|
2022
|
Vladimir Braverman
Vincent Cohen-Addad
Shaofeng H. -C. Jiang
Robert Krauthgamer
Chris Schwiegelshohn
Mads Bech Toftrup
Xuan Wu
|
|
+
|
Streaming Euclidean Max-Cut: Dimension vs Data Reduction
|
2022
|
Yu Chen
Shaofeng H. -C. Jiang
Robert Krauthgamer
|
|
+
|
An Algorithmic Bridge Between Hamming and Levenshtein Distances
|
2022
|
Elazar Goldenberg
Tomasz Kociumaka
Robert Krauthgamer
Barna Saha
|
|
+
|
Clustering Permutations: New Techniques with Streaming Applications
|
2022
|
Diptarka Chakraborty
Debarati Das
Robert Krauthgamer
|
|
+
|
Recovery Guarantees for Distributed-OMP
|
2022
|
Chen Amiraz
Robert Krauthgamer
Boaz Nadler
|
|
+
|
Gomory-Hu Tree in Subcubic Time
|
2021
|
Amir Abboud
Robert Krauthgamer
Jason Li
Debmalya Panigrahi
Thatchaphol Saranurak
Ohad Trabelsi
|
|
+
|
Friendly Cut Sparsifiers and Faster Gomory-Hu Trees
|
2021
|
Amir Abboud
Robert Krauthgamer
Ohad Trabelsi
|
|
+
PDF
Chat
|
Subcubic algorithms for GomoryâHu tree in unweighted graphs
|
2021
|
Amir Abboud
Robert Krauthgamer
Ohad Trabelsi
|
|
+
PDF
Chat
|
Towards tight bounds for spectral sparsification of hypergraphs
|
2021
|
Michael Kapralov
Robert Krauthgamer
Jakab Tardos
Yuichi Yoshida
|
|
+
|
APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time.
|
2021
|
Amir Abboud
Robert Krauthgamer
Ohad Trabelsi
|
|
+
|
Spectral Hypergraph Sparsifiers of Nearly Linear Size.
|
2021
|
Michael Kapralov
Robert Krauthgamer
Jakab Tardos
Yuichi Yoshida
|
|
+
|
Smoothness of Schatten Norms and Sliding-Window Matrix Streams.
|
2021
|
Robert Krauthgamer
Shay Sapir
|
|
+
|
Sparse Normal Means Estimation with Sublinear Communication.
|
2021
|
Chen Amiraz
Robert Krauthgamer
Boaz Nadler
|
|
+
PDF
Chat
|
Approximating the Median under the Ulam Metric
|
2021
|
Diptarka Chakraborty
Debarati Das
Robert Krauthgamer
|
|
+
PDF
Chat
|
Coresets for Clustering in Excluded-minor Graphs and Beyond
|
2021
|
Vladimir Braverman
Shaofeng H.-C. Jiang
Robert Krauthgamer
Xuan Wu
|
|
+
|
Coresets for Clustering with Missing Values
|
2021
|
Vladimir Braverman
Shaofeng H.-C. Jiang
Robert Krauthgamer
Xuan Wu
|
|
+
|
Approximate Trace Reconstruction via Median String (in Average-Case)
|
2021
|
Diptarka Chakraborty
Debarati Das
Robert Krauthgamer
|
|
+
|
Coresets for Kernel Clustering
|
2021
|
Shaofeng H.-C. Jiang
Robert Krauthgamer
Jianing Lou
Yubo Zhang
|
|
+
|
Approximate Trace Reconstruction via Median String (In Average-Case).
|
2021
|
Diptarka Chakraborty
Debarati Das
Robert Krauthgamer
|
|
+
|
Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal
|
2021
|
Elazar Goldenberg
Tomasz Kociumaka
Robert Krauthgamer
Barna Saha
|
|
+
|
Friendly Cut Sparsifiers and Faster Gomory-Hu Trees
|
2021
|
Amir Abboud
Robert Krauthgamer
Ohad Trabelsi
|
|
+
|
Spectral Hypergraph Sparsifiers of Nearly Linear Size
|
2021
|
Michael Kapralov
Robert Krauthgamer
Jakab Tardos
Yuichi Yoshida
|
|
+
|
Smoothness of Schatten Norms and Sliding-Window Matrix Streams
|
2021
|
Robert Krauthgamer
Shay Sapir
|
|
+
|
Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time
|
2021
|
Amir Abboud
Robert Krauthgamer
Jason Li
Debmalya Panigrahi
Thatchaphol Saranurak
Ohad Trabelsi
|
|
+
|
Distributed Sparse Normal Means Estimation with Sublinear Communication
|
2021
|
Chen Amiraz
Robert Krauthgamer
Boaz Nadler
|
|
+
|
Flow Metrics on Graphs
|
2021
|
Lior Kalman
Robert Krauthgamer
|
|
+
|
APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time
|
2021
|
Amir Abboud
Robert Krauthgamer
Ohad Trabelsi
|
|
+
|
Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs
|
2020
|
Amir Abboud
Robert Krauthgamer
Ohad Trabelsi
|
|
+
|
Approximating the Median under the Ulam Metric
|
2020
|
Diptarka Chakraborty
Debarati Das
Robert Krauthgamer
|
|
+
PDF
Chat
|
Cut-Equivalent Trees are Optimal for Min-Cut Queries
|
2020
|
Amir Abboud
Robert Krauthgamer
Ohad Trabelsi
|
|
+
|
Cut-Equivalent Trees are Optimal for Min-Cut Queries
|
2020
|
Amir Abboud
Robert Krauthgamer
Ohad Trabelsi
|
|
+
PDF
Chat
|
Tight recovery guarantees for orthogonal matching pursuit under Gaussian noise
|
2020
|
Chen Amiraz
Robert Krauthgamer
Boaz Nadler
|
|
+
|
Faster Algorithms for Orienteering and k-TSP.
|
2020
|
Lee-Ad Gottlieb
Robert Krauthgamer
Havana Rika
|
|
+
PDF
Chat
|
Refined Vertex Sparsifiers of Planar Graphs
|
2020
|
Robert Krauthgamer
Havana Rika
|
|
+
|
Coresets for Clustering in Excluded-minor Graphs and Beyond
|
2020
|
Vladimir Braverman
Shaofeng H.-C. Jiang
Robert Krauthgamer
Xuan Wu
|
|
+
|
Towards Tight Bounds for Spectral Sparsification of Hypergraphs
|
2020
|
Michael Kapralov
Robert Krauthgamer
Jakab Tardos
Yuichi Yoshida
|
|
+
|
Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs
|
2020
|
Amir Abboud
Robert Krauthgamer
Ohad Trabelsi
|
|
+
|
Streaming Algorithms for Geometric Steiner Forest
|
2020
|
Artur Czumaj
Shaofeng H. -C. Jiang
Robert Krauthgamer
Pavel VeselĂ˝
|
|
+
|
Near-Optimal Entrywise Sampling of Numerically Sparse Matrices
|
2020
|
Vladimir Braverman
Robert Krauthgamer
Aditya Krishnan
Shay Sapir
|
|
+
|
Approximating the Median under the Ulam Metric
|
2020
|
Diptarka Chakraborty
Debarati Das
Robert Krauthgamer
|
|
+
|
Cut-Equivalent Trees are Optimal for Min-Cut Queries
|
2020
|
Amir Abboud
Robert Krauthgamer
Ohad Trabelsi
|
|
+
|
Faster Algorithms for Orienteering and $k$-TSP
|
2020
|
Lee-Ad Gottlieb
Robert Krauthgamer
Havana Rika
|
|
+
PDF
Chat
|
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs
|
2019
|
Amir Abbou
Robert Krauthgamer
Ohad Trabelsi
|
|
+
PDF
Chat
|
Labelings vs. Embeddings: On Distributed Representations of Distances
|
2019
|
Arnold Filtser
Lee-Ad Gottlieb
Robert Krauthgamer
|
|
+
PDF
Chat
|
Sublinear Algorithms for Gap Edit Distance
|
2019
|
Elazar Goldenberg
Robert Krauthgamer
Barna Saha
|
|
+
|
Sublinear Algorithms for Gap Edit Distance
|
2019
|
Elazar Goldenberg
Robert Krauthgamer
Barna Saha
|
|
+
|
Labelings vs. Embeddings: On Distributed Representations of Distances
|
2019
|
Arnold Filtser
Lee-Ad Gottlieb
Robert Krauthgamer
|
|
+
|
Flow-cut gaps and face covers in planar graphs
|
2019
|
Robert Krauthgamer
James R. Lee
Havana Rika
|
|
+
|
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs
|
2019
|
Amir Abboud
Robert Krauthgamer
Ohad Trabelsi
|
|
+
PDF
Chat
|
Flow-Cut Gaps and Face Covers in Planar Graphs
|
2019
|
Robert Krauthgamer
James R. Lee
Havana Rika
|
|
+
|
Coresets for Ordered Weighted Clustering
|
2019
|
Vladimir Braverman
Shaofeng H.-C. Jiang
Robert Krauthgamer
Xuan Wu
|
|
+
|
Tight Recovery Guarantees for Orthogonal Matching Pursuit Under Gaussian Noise
|
2019
|
Chen Amiraz
Robert Krauthgamer
Boaz Nadler
|
|
+
|
Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension
|
2019
|
Vladimir Braverman
Robert Krauthgamer
Aditya Krishnan
Roi Sinoff
|
|
+
|
Coresets for Clustering in Graphs of Bounded Treewidth
|
2019
|
D. N. Baker
Vladimir Braverman
Lingxiao Huang
Shaofeng H.-C. Jiang
Robert Krauthgamer
Xuan Wu
|
|
+
|
Sublinear Algorithms for Gap Edit Distance
|
2019
|
Elazar Goldenberg
Robert Krauthgamer
Barna Saha
|
|
+
|
Labelings vs. Embeddings: On Distributed Representations of Distances
|
2019
|
Arnold Filtser
Lee-Ad Gottlieb
Robert Krauthgamer
|
|
+
|
Almost-Smooth Histograms and Sliding-Window Graph Algorithms
|
2019
|
Robert Krauthgamer
David Reitblat
|
|
+
|
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs
|
2019
|
Amir Abboud
Robert Krauthgamer
Ohad Trabelsi
|
|
+
|
On Solving Linear Systems in Sublinear Time
|
2018
|
Alexandr Andoni
Robert Krauthgamer
Yosef Pogrow
|
|
+
|
On Solving Linear Systems in Sublinear Time
|
2018
|
Alexandr Andoni
Robert Krauthgamer
Yosef Pogrow
|
|
+
|
Noisy Voronoi: a Simple Framework for Terminal-Clustering Problems.
|
2018
|
Arnold Filtser
Robert Krauthgamer
Ohad Trabelsi
|
|
+
|
Relaxed Voronoi: a Simple Framework for Terminal-Clustering Problems
|
2018
|
Arnold Filtser
Robert Krauthgamer
Ohad Trabelsi
|
|
+
PDF
Chat
|
Conditional Lower Bounds for All-Pairs Max-Flow
|
2018
|
Robert Krauthgamer
Ohad Trabelsi
|
|
+
PDF
Chat
|
Sketching and Embedding are Equivalent for Norms
|
2018
|
Alexandr Andoni
Robert Krauthgamer
Ilya Razenshteyn
|
|
+
|
Batch Sparse Recovery, or How to Leverage the Average Sparsity
|
2018
|
Alexandr Andoni
Lior Kamma
Robert Krauthgamer
Eric Price
|
|
+
|
Universal Streaming of Subset Norms
|
2018
|
Vladimir Braverman
Robert Krauthgamer
Lin F. Yang
|
|
+
|
Faster Algorithms for All-Pairs Bounded Min-Cuts
|
2018
|
Amir Abboud
Loukas Georgiadis
Giuseppe F. Italiano
Robert Krauthgamer
Nikos Parotsidis
Ohad Trabelsi
PrzemysĹaw UznaĹski
Daniel Wolleb-Graf
|
|
+
|
Flow-Cut Gaps and Face Covers in Planar Graphs
|
2018
|
Robert Krauthgamer
James R. Lee
Havana Rika
|
|
+
|
On Solving Linear Systems in Sublinear Time
|
2018
|
Alexandr Andoni
Robert Krauthgamer
Yosef Pogrow
|
|
+
|
Relaxed Voronoi: a Simple Framework for Terminal-Clustering Problems
|
2018
|
Arnold Filtser
Robert Krauthgamer
Ohad Trabelsi
|
|
+
|
Revisiting the Set Cover Conjecture.
|
2017
|
Robert Krauthgamer
Ohad Trabelsi
|
|
+
PDF
Chat
|
Streaming symmetric norms via measure concentration
|
2017
|
JarosĹaw BĹasiok
Vladimir Braverman
Stephen R. Chestnut
Robert Krauthgamer
Lin F. Yang
|
|
+
PDF
Chat
|
Efficient Regression in Metric Spaces via Approximate Lipschitz Extension
|
2017
|
Lee-Ad Gottlieb
Aryeh Kontorovich
Robert Krauthgamer
|
|
+
|
Conditional Lower Bounds for All-Pairs Max-Flow
|
2017
|
Robert Krauthgamer
Ohad Trabelsi
|
|
+
|
Refined Vertex Sparsifiers of Planar Graphs
|
2017
|
Robert Krauthgamer
Havana
rika
|
|
+
|
Conditional Lower Bound for Subgraph Isomorphism with a Tree Pattern
|
2017
|
Robert Krauthgamer
Ohad Trabelsi
|
|
+
|
The Set Cover Conjecture and Subgraph Isomorphism with a Tree Pattern
|
2017
|
Robert Krauthgamer
Ohad Trabelsi
|
|
+
|
Conditional Lower Bounds for All-Pairs Max-Flow
|
2017
|
Robert Krauthgamer
Ohad Trabelsi
|
|
+
PDF
Chat
|
Cheeger-Type Approximation for Sparsest <i>st</i> -Cut
|
2016
|
Robert Krauthgamer
Tal Wagner
|
|
+
PDF
Chat
|
Metric Decompositions of Path-Separable Graphs
|
2016
|
Lior Kamma
Robert Krauthgamer
|
|
+
|
Sketches for Matrix Norms: Faster, Smaller and More General.
|
2016
|
Vladimir Braverman
Stephen R. Chestnut
Robert Krauthgamer
Lin F. Yang
|
|
+
|
Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order
|
2016
|
Vladimir Braverman
Stephen R. Chestnut
Robert Krauthgamer
Yi Li
David P. Woodruff
Lin F. Yang
|
|
+
PDF
Chat
|
On Sketching Quadratic Forms
|
2016
|
Alexandr Andoni
Jiecao Chen
Robert Krauthgamer
Bo Qin
David P. Woodruff
Qin Zhang
|
|
+
PDF
Chat
|
Tight Bounds for Gomory-Hu-like Cut Counting
|
2016
|
Rajesh Chitnis
Lior Kamma
Robert Krauthgamer
|
|
+
PDF
Chat
|
The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme
|
2016
|
Yair Bartal
Lee-Ad Gottlieb
Robert Krauthgamer
|
|
+
|
Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order
|
2016
|
Vladimir Braverman
Stephen R. Chestnut
Robert Krauthgamer
Yi Li
David P. Woodruff
Lin F. Yang
|
|
+
|
Tight Bounds for Gomory-Hu-like Cut Counting
|
2015
|
Rajesh Chitnis
Lior Kamma
Robert Krauthgamer
|
|
+
|
Adaptive metric dimensionality reduction
|
2015
|
Lee-Ad Gottlieb
Aryeh Kontorovich
Robert Krauthgamer
|
|
+
|
Streaming Symmetric Norms via Measure Concentration
|
2015
|
JarosĹaw BĹasiok
Vladimir Braverman
Stephen R. Chestnut
Robert Krauthgamer
Lin F. Yang
|
|
+
|
Sparsification of Two-Variable Valued CSPs.
|
2015
|
Arnold Filtser
Robert Krauthgamer
|
|
+
PDF
Chat
|
A Nonlinear Approach to Dimension Reduction
|
2015
|
Lee-Ad Gottlieb
Robert Krauthgamer
|
|
+
PDF
Chat
|
Sketching and Embedding are Equivalent for Norms
|
2015
|
Alexandr Andoni
Robert Krauthgamer
Ilya Razenshteyn
|
|
+
|
Do semidefinite relaxations solve sparse PCA up to the information limit?
|
2015
|
Robert Krauthgamer
Boaz Nadler
Dan Vilenchik
|
|
+
|
Metric Decompositions of Path-Separable Graphs
|
2015
|
Lior Kamma
Robert Krauthgamer
|
|
+
PDF
Chat
|
Sketching Cuts in Graphs and Hypergraphs
|
2015
|
Dmitry Kogan
Robert Krauthgamer
|
|
+
|
Towards Resistance Sparsifiers
|
2015
|
Michael Dinitz
Robert Krauthgamer
Tal Wagner
|
|
+
PDF
Chat
|
Cutting Corners Cheaply, or How to Remove Steiner Points
|
2015
|
Lior Kamma
Robert Krauthgamer
Huy L. Nguyáť
n
|
|
+
|
On Sketching Quadratic Forms
|
2015
|
Alexandr Andoni
Jiecao Chen
Robert Krauthgamer
Bo Qin
David P. Woodruff
Qin Zhang
|
|
+
|
Sparsification of Two-Variable Valued CSPs
|
2015
|
Arnold Filtser
Robert Krauthgamer
|
|
+
|
Metric Decompositions of Path-Separable Graphs
|
2015
|
Lior Kamma
Robert Krauthgamer
|
|
+
|
Tight Bounds for Gomory-Hu-like Cut Counting
|
2015
|
Rajesh Chitnis
Lior Kamma
Robert Krauthgamer
|
|
+
|
Streaming Symmetric Norms via Measure Concentration
|
2015
|
JarosĹaw BĹasiok
Vladimir Braverman
Stephen R. Chestnut
Robert Krauthgamer
Lin F. Yang
|
|
+
|
Sketching and Embedding are Equivalent for Norms
|
2014
|
Alexandr Andoni
Robert Krauthgamer
Ilya Razenshteyn
|
|
+
|
Cheeger-type approximation for sparsest $st$-cut
|
2014
|
Robert Krauthgamer
Tal Wagner
|
|
+
PDF
Chat
|
Spectral Approaches to Nearest Neighbor Search
|
2014
|
Amirali Abdullah
Alexandr Andoni
Ravindran Kannan
Robert Krauthgamer
|
|
+
|
Spectral Approaches to Nearest Neighbor Search
|
2014
|
Amirali Abdullah
Alexandr Andoni
Ravindran Kannan
Robert Krauthgamer
|
|
+
PDF
Chat
|
Efficient Classification for Metric Data
|
2014
|
Lee-Ad Gottlieb
Aryeh Kontorovich
Robert Krauthgamer
|
|
+
|
The Sketching Complexity of Graph Cuts
|
2014
|
Alexandr Andoni
Robert Krauthgamer
David P. Woodruff
|
|
+
|
Towards (1 + Îľ)-approximate flow sparsifiers
|
2014
|
Alexandr Andoni
Anupam Gupta
Robert Krauthgamer
|
|
+
PDF
Chat
|
Orienting Fully Dynamic Graphs with Worst-Case Time Bounds
|
2014
|
Tsvi Kopelowitz
Robert Krauthgamer
Ely Porat
Shay Solomon
|
|
+
PDF
Chat
|
Preserving Terminal Distances Using Minors
|
2014
|
Robert Krauthgamer
Huy L. Nguyáť
n
Tamar Zondiner
|
|
+
|
Sketching Cuts in Graphs and Hypergraphs
|
2014
|
Dmitry Kogan
Robert Krauthgamer
|
|
+
|
Vertex Sparsifiers: New Results from Old Techniques
|
2014
|
Matthias Englert
Anupam Gupta
Robert Krauthgamer
Harald Räcke
Inbal Talgam-Cohen
Kunal Talwar
|
|
+
|
The Sketching Complexity of Graph Cuts
|
2014
|
Alexandr Andoni
Robert Krauthgamer
David P. Woodruff
|
|
+
|
Cheeger-type approximation for sparsest $st$-cut
|
2014
|
Robert Krauthgamer
Tal Wagner
|
|
+
|
Sketching and Embedding are Equivalent for Norms
|
2014
|
Alexandr Andoni
Robert Krauthgamer
Ilya Razenshteyn
|
|
+
|
Spectral Approaches to Nearest Neighbor Search
|
2014
|
Amirali Abdullah
Alexandr Andoni
Ravindran Kannan
Robert Krauthgamer
|
|
+
PDF
Chat
|
Cutting corners cheaply, or how to remove Steiner points
|
2013
|
Lior Kamma
Robert Krauthgamer
Huy L. Nguyáť
n
|
|
+
|
Orienting Fully Dynamic Graphs with Worst-Case Time Bounds
|
2013
|
Tsvi Kopelowitz
Robert Krauthgamer
Ely Porat
Shay Solomon
|
|
+
|
Towards (1+\epsilon)-Approximate Flow Sparsifiers
|
2013
|
Alexandr Andoni
Anupam Gupta
Robert Krauthgamer
|
|
+
|
Do Semidefinite Relaxations Really Solve Sparse PCA
|
2013
|
Robert Krauthgamer
Boaz Nadler
Dan Vilenchik
|
|
+
|
Adaptive Metric Dimensionality Reduction
|
2013
|
Lee-Ad Gottlieb
Aryeh Kontorovich
Robert Krauthgamer
|
|
+
PDF
Chat
|
Mimicking Networks and Succinct Representations of Terminal Cuts
|
2013
|
Robert Krauthgamer
Havana Rika
|
|
+
PDF
Chat
|
Efficient Regression in Metric Spaces via Approximate Lipschitz Extension
|
2013
|
Lee-Ad Gottlieb
Aryeh Kontorovich
Robert Krauthgamer
|
|
+
PDF
Chat
|
Adaptive Metric Dimensionality Reduction
|
2013
|
Lee-Ad Gottlieb
Aryeh Kontorovich
Robert Krauthgamer
|
|
+
|
Adaptive Metric Dimensionality Reduction
|
2013
|
Lee-Ad Gottlieb
Aryeh Kontorovich
Robert Krauthgamer
|
|
+
|
Cutting corners cheaply, or how to remove Steiner points
|
2013
|
Lior Kamma
Robert Krauthgamer
Huy L. Nguyáť
n
|
|
+
|
Efficient Classification for Metric Data
|
2013
|
Lee-Ad Gottlieb
Aryeh Kontorovich
Robert Krauthgamer
|
|
+
|
Orienting Fully Dynamic Graphs with Worst-Case Time Bounds
|
2013
|
Tsvi Kopelowitz
Robert Krauthgamer
Ely Porat
Shay Solomon
|
|
+
|
Towards (1+Îľ)-Approximate Flow Sparsifiers
|
2013
|
Alexandr Andoni
Anupam Gupta
Robert Krauthgamer
|
|
+
PDF
Chat
|
Everywhere-Sparse Spanners via Dense Subgraphs
|
2012
|
Eden ChlamtĂĄÄ
Michael Dinitz
Robert Krauthgamer
|
|
+
|
Faster Clustering via Preprocessing
|
2012
|
Tsvi Kopelowitz
Robert Krauthgamer
|
|
+
|
Everywhere-Sparse Spanners via Dense Subgraphs
|
2012
|
Eden ChlamtĂĄÄ
Michael Dinitz
Robert Krauthgamer
|
|
+
|
Preserving Terminal Distances using Minors
|
2012
|
Robert Krauthgamer
Tamar Zondiner
|
|
+
PDF
Chat
|
Preserving Terminal Distances Using Minors
|
2012
|
Robert Krauthgamer
Tamar Zondiner
|
|
+
|
Faster Clustering via Preprocessing
|
2012
|
Tsvi Kopelowitz
Robert Krauthgamer
|
|
+
|
Preserving Terminal Distances using Minors
|
2012
|
Robert Krauthgamer
Tamar Zondiner
|
|
+
|
Everywhere-Sparse Spanners via Dense Subgraphs
|
2012
|
Eden ChlamtĂĄÄ
Michael Dinitz
Robert Krauthgamer
|
|
+
|
Mimicking Networks and Succinct Representations of Terminal Cuts
|
2012
|
Robert Krauthgamer
Havana Rika
|
|
+
|
Min-Max Graph Partitioning and Small Set Expansion
|
2011
|
Nikhil Bansal
Uriel Feige
Robert Krauthgamer
Konstantin Makarychev
Viswanath Nagarajan
Joseph Joseph
Naor
Roy Schwartz
|
|
+
|
Directed spanners via flow-based linear programs
|
2011
|
Michael Dinitz
Robert Krauthgamer
|
|
+
PDF
Chat
|
A Nonlinear Approach to Dimension Reduction
|
2011
|
Lee-Ad Gottlieb
Robert Krauthgamer
|
|
+
|
Fault-Tolerant Spanners: Better and Simpler
|
2011
|
Michael Dinitz
Robert Krauthgamer
|
|
+
|
Min-Max Graph Partitioning and Small Set Expansion
|
2011
|
Nikhil Bansal
Uriel Feige
Robert Krauthgamer
Konstantin Makarychev
Viswanath Nagarajan
Naor
Roy Schwartz
|
|
+
|
Efficient Regression in Metric Spaces via Approximate Lipschitz Extension
|
2011
|
Lee-Ad Gottlieb
Aryeh Kontorovich
Robert Krauthgamer
|
|
+
|
Directed Spanners via Flow-Based Linear Programs
|
2010
|
Michael Dinitz
Robert Krauthgamer
|
|
+
|
Streaming Algorithms from Precision Sampling
|
2010
|
Alexandr Andoni
Robert Krauthgamer
Krzysztof Onak
|
|
+
PDF
Chat
|
Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
|
2010
|
Alexandr Andoni
Robert Krauthgamer
Krzysztof Onak
|
|
+
PDF
Chat
|
Vertex Sparsifiers: New Results from Old Techniques
|
2010
|
Matthias Englert
Anupam Gupta
Robert Krauthgamer
Harald Räcke
Inbal Talgam-Cohen
Kunal Talwar
|
|
+
PDF
Chat
|
Approximating Sparsest Cut in Graphs of Bounded Treewidth
|
2010
|
Eden ChlamtĂĄÄ
Robert Krauthgamer
Prasad Raghavendra
|
|
+
PDF
Chat
|
Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
|
2010
|
Alexandr Andoni
Robert Krauthgamer
Krzysztof Onak
|
|
+
|
Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
|
2010
|
Alexandr Andoni
Robert Krauthgamer
Krzysztof Onak
|
|
+
|
Streaming Algorithms from Precision Sampling
|
2010
|
Alexandr Andoni
Robert Krauthgamer
Krzysztof Onak
|
|
+
|
Directed Spanners via Flow-Based Linear Programs
|
2010
|
Michael Dinitz
Robert Krauthgamer
|
|
+
|
Approximating Sparsest Cut in Graphs of Bounded Treewidth
|
2010
|
Eden ChlamtĂĄÄ
Robert Krauthgamer
Prasad Raghavendra
|
|
+
PDF
Chat
|
Measured descent: a new embedding method for finite metrics
|
2005
|
Robert Krauthgamer
J. R. Lee
Manor Mendel
Assaf Naor
|
|
+
PDF
Chat
|
Measured Descent: A New Embedding Method for Finite Metrics
|
2004
|
Robert Krauthgamer
J.R. Lee
Manor Mendel
Assaf Naor
|
|
+
PDF
Chat
|
Bounded geometries, fractals, and low-distortion embeddings
|
2004
|
Anupam Gupta
Robert Krauthgamer
J.R. Lee
|
|
+
|
The intrinsic dimensionality of graphs
|
2003
|
Robert Krauthgamer
James R. Lee
|
|
+
|
Polylogarithmic inapproximability
|
2003
|
Eran Halperin
Robert Krauthgamer
|
|
+
PDF
Chat
|
Stereoscopic families of permutations, and their applications
|
2002
|
Uriel Feige
Robert Krauthgamer
|
|
+
|
On approximating the achromatic number
|
2001
|
Guy Kortsarz
Robert Krauthgamer
|
|
+
|
On Approximating the Achromatic Number
|
2001
|
Guy Kortsarz
Robert Krauthgamer
|