Robert Krauthgamer

266 papers A* 82A 11B 7C 1Journal 145Unranked 17

Year	Rank	Type	Title / Venue / Authors
2026	A*	`conf`	All-Pairs Minimum Cut using Õ(n SODA Yotam Kenneth-Mordoch, Robert Krauthgamer
2026	A	`conf`	Dimension Reduction for Clustering: The Curious Case of Discrete Centers. ITCS Shaofeng H.-C. Jiang, Robert Krauthgamer, Shay Sapir, Sandeep Silwal, Di Yue
2026	J	`jnl`	Fast Nearest Neighbor Search for ℓ CoRR Robert Krauthgamer, Nir Petruschka
2026	—	`conf`	Simple Algorithms for Fully Dynamic Edge Connectivity. SOSA Yotam Kenneth-Mordoch, Robert Krauthgamer
2025	J	`jnl`	All-Pairs Minimum Cut using O(n CoRR Yotam Kenneth-Mordoch, Robert Krauthgamer
2025	A	`conf`	Coresets for 1-Center in 𝓁₁ Metrics. ITCS Amir Carmel, Chengzhi Guo, Shaofeng H.-C. Jiang, Robert Krauthgamer
2025	A	`conf`	Cut-Query Algorithms with Few Rounds. ESA Yotam Kenneth-Mordoch, Robert Krauthgamer
2025	J	`jnl`	Cut-Query Algorithms with Few Rounds. CoRR Yotam Kenneth-Mordoch, Robert Krauthgamer
2025	J	`jnl`	Dimension Reduction for Clustering: The Curious Case of Discrete Centers. CoRR Shaofeng H.-C. Jiang, Robert Krauthgamer, Shay Sapir, Sandeep Silwal, Di Yue
2025	J	`jnl`	Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow. CoRR Yotam Kenneth-Mordoch, Robert Krauthgamer
2025	J	`jnl`	Lipschitz Decompositions of Finite ℓ CoRR Robert Krauthgamer, Nir Petruschka
2025	A*	`conf`	Lipschitz Decompositions of Finite 𝓁 SoCG Robert Krauthgamer, Nir Petruschka
2025	A*	`conf`	Near-Optimal Dimension Reduction for Facility Location. STOC Lingxiao Huang, Shaofeng H.-C. Jiang, Robert Krauthgamer, Di Yue
2025	J	`jnl`	Simple Algorithms for Fully Dynamic Edge Connectivity. CoRR Yotam Kenneth-Mordoch, Robert Krauthgamer
2025	J	`jnl`	Stable coresets: Unleashing the power of uniform sampling. CoRR Amir Carmel, Robert Krauthgamer
2025	J	`jnl`	The General Expiration Streaming Model: Diameter, CoRR Lotte Blank, Sergio Cabello, MohammadTaghi Hajiaghayi, Robert Krauthgamer, Sepideh Mahabadi, André Nusser, Jeff M. Phillips, Jonas Sauer
2025	J	`jnl`	The Power of Recursive Embeddings for ℓ CoRR Robert Krauthgamer, Nir Petruschka, Shay Sapir
2025	A*	`conf`	The Power of Recursive Embeddings for ℓp Metrics. FOCS Robert Krauthgamer, Nir Petruschka, Shay Sapir
2024	J	`jnl`	Coresets for kernel clustering. Mach. Learn. Shaofeng H.-C. Jiang, Robert Krauthgamer, Jianing Lou, Yubo Zhang
2024	A*	`conf`	Cut Sparsification and Succinct Representation of Submodular Hypergraphs. ICALP Yotam Kenneth, Robert Krauthgamer
2024	A*	`conf`	Fully-Scalable MPC Algorithms for Clustering in High Dimension. ICALP Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý
2024	J	`jnl`	Labelings vs. Embeddings: On Distributed and Prioritized Representations of Distances. Discret. Comput. Geom. Arnold Filtser, Lee-Ad Gottlieb, Robert Krauthgamer
2024	A*	`conf`	Moderate Dimension Reduction for k-Center Clustering. SoCG Shaofeng H.-C. Jiang, Robert Krauthgamer, Shay Sapir
2024	J	`jnl`	Near-Optimal Dimension Reduction for Facility Location. CoRR Lingxiao Huang, Shaofeng H.-C. Jiang, Robert Krauthgamer, Di Yue
2024	A	`conf`	Recovery Guarantees for Distributed-OMP. AISTATS Chen Amiraz, Robert Krauthgamer, Boaz Nadler
2024	J	`jnl`	Streaming Algorithms for Geometric Steiner Forest. ACM Trans. Algorithms Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý
2023	A	`conf`	An Algorithmic Bridge Between Hamming and Levenshtein Distances. ITCS Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha
2023	A	`conf`	Clustering Permutations: New Techniques with Streaming Applications. ITCS Diptarka Chakraborty, Debarati Das, Robert Krauthgamer
2023	J	`jnl`	Comparison of Matrix Norm Sparsification. Algorithmica Robert Krauthgamer, Shay Sapir
2023	J	`jnl`	Cut Sparsification and Succinct Representation of Submodular Hypergraphs. CoRR Yotam Kenneth, Robert Krauthgamer
2023	A*	`conf`	Exact Flow Sparsification Requires Unbounded Size. SODA Robert Krauthgamer, Ron Mosenzon
2023	J	`jnl`	Fully Scalable MPC Algorithms for Clustering in High Dimension. CoRR Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý
2023	A*	`conf`	Lower Bounds for Pseudo-Deterministic Counting in a Stream. ICALP Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, Shay Sapir
2023	J	`jnl`	Lower Bounds for Pseudo-Deterministic Counting in a Stream. CoRR Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, Shay Sapir
2023	J	`jnl`	Moderate Dimension Reduction for k-Center Clustering. CoRR Shaofeng H.-C. Jiang, Robert Krauthgamer, Shay Sapir
2023	A*	`conf`	Streaming Euclidean Max-Cut: Dimension vs Data Reduction. STOC Xiaoyu Chen, Shaofeng H.-C. Jiang, Robert Krauthgamer
2022	J	`jnl`	Almost-Smooth Histograms and Sliding-Window Graph Algorithms. Algorithmica Robert Krauthgamer, David Reitblat
2022	A*	`conf`	Almost-linear STOC Hsien-Chih Chang, Robert Krauthgamer, Zihan Tan
2022	J	`jnl`	An Algorithmic Bridge Between Hamming and Levenshtein Distances. CoRR Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha
2022	A*	`conf`	Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time. FOCS Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, Ohad Trabelsi
2022	J	`jnl`	Clustering Permutations: New Techniques with Streaming Applications. CoRR Diptarka Chakraborty, Debarati Das, Robert Krauthgamer
2022	J	`jnl`	Comparison of Matrix Norm Sparsification. CoRR Robert Krauthgamer, Shay Sapir
2022	J	`jnl`	Distributed Sparse Linear Regression with Sublinear Communication. CoRR Chen Amiraz, Robert Krauthgamer, Boaz Nadler
2022	J	`jnl`	Exact Flow Sparsification Requires Unbounded Size. CoRR Robert Krauthgamer, Ron Mosenzon
2022	J	`jnl`	Faster algorithms for orienteering and Theor. Comput. Sci. Lee-Ad Gottlieb, Robert Krauthgamer, Havana Rika
2022	A*	`conf`	Friendly Cut Sparsifiers and Faster Gomory-Hu Trees. SODA Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
2022	A*	`conf`	Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal. FOCS Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha
2022	J	`jnl`	Near-Linear ε-Emulators for Planar Graphs. CoRR Hsien-Chih Chang, Robert Krauthgamer, Zihan Tan
2022	J	`jnl`	Optimal Vertex-Cut Sparsification of Quasi-Bipartite Graphs. CoRR Itai Boneh, Robert Krauthgamer
2022	J	`jnl`	Smoothness of Schatten norms and sliding-window matrix streams. Inf. Process. Lett. Robert Krauthgamer, Shay Sapir
2022	A*	`conf`	Streaming Algorithms for Geometric Steiner Forest. ICALP Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý
2022	J	`jnl`	Streaming Euclidean Max-Cut: Dimension vs Data Reduction. CoRR Xiaoyu Chen, Shaofeng H.-C. Jiang, Robert Krauthgamer
2022	A*	`conf`	Streaming Facility Location in High Dimension via Geometric Hashing. FOCS Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý, Mingwei Yang
2022	J	`jnl`	Streaming Facility Location in High Dimension via New Geometric Hashing. CoRR Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý, Mingwei Yang
2022	A*	`conf`	The Power of Uniform Sampling for Coresets. FOCS Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, Xuan Wu
2022	J	`jnl`	The Power of Uniform Sampling for Coresets. CoRR Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, Xuan Wu
2022	J	`jnl`	Universal Streaming of Subset Norms. Theory Comput. Vladimir Braverman, Robert Krauthgamer, Lin F. Yang
2021	A*	`conf`	APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time. FOCS Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
2021	J	`jnl`	APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time. CoRR Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
2021	—	`conf`	Approximate Trace Reconstruction via Median String (In Average-Case). FSTTCS Diptarka Chakraborty, Debarati Das, Robert Krauthgamer
2021	J	`jnl`	Approximate Trace Reconstruction via Median String (in Average-Case). CoRR Diptarka Chakraborty, Debarati Das, Robert Krauthgamer
2021	A*	`conf`	Approximating the Median under the Ulam Metric. SODA Diptarka Chakraborty, Debarati Das, Robert Krauthgamer
2021	A*	`conf`	Coresets for Clustering in Excluded-minor Graphs and Beyond. SODA Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu
2021	A*	`conf`	Coresets for Clustering with Missing Values. NeurIPS Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu
2021	J	`jnl`	Coresets for Clustering with Missing Values. CoRR Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu
2021	J	`jnl`	Coresets for Kernel Clustering. CoRR Shaofeng H.-C. Jiang, Robert Krauthgamer, Jianing Lou, Yubo Zhang
2021	J	`jnl`	Flow Metrics on Graphs. CoRR Lior Kalman, Robert Krauthgamer
2021	J	`jnl`	Friendly Cut Sparsifiers and Faster Gomory-Hu Trees. CoRR Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
2021	J	`jnl`	Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal. CoRR Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha
2021	J	`jnl`	Gomory-Hu Tree in Subcubic Time. CoRR Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, Ohad Trabelsi
2021	A*	`conf`	Near-Optimal Entrywise Sampling of Numerically Sparse Matrices. COLT Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, Shay Sapir
2021	J	`jnl`	New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs. Theory Comput. Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
2021	J	`jnl`	Smoothness of Schatten Norms and Sliding-Window Matrix Streams. CoRR Robert Krauthgamer, Shay Sapir
2021	J	`jnl`	Sparse Normal Means Estimation with Sublinear Communication. CoRR Chen Amiraz, Robert Krauthgamer, Boaz Nadler
2021	A*	`conf`	Spectral Hypergraph Sparsifiers of Nearly Linear Size. FOCS Michael Kapralov, Robert Krauthgamer, Jakab Tardos, Yuichi Yoshida
2021	J	`jnl`	Spectral Hypergraph Sparsifiers of Nearly Linear Size. CoRR Michael Kapralov, Robert Krauthgamer, Jakab Tardos, Yuichi Yoshida
2021	A*	`conf`	Subcubic algorithms for Gomory-Hu tree in unweighted graphs. STOC Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
2021	A*	`conf`	Towards tight bounds for spectral sparsification of hypergraphs. STOC Michael Kapralov, Robert Krauthgamer, Jakab Tardos, Yuichi Yoshida
2020	J	`jnl`	Approximating the Median under the Ulam Metric. CoRR Diptarka Chakraborty, Debarati Das, Robert Krauthgamer
2020	J	`jnl`	Coresets for Clustering in Excluded-minor Graphs and Beyond. CoRR Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu
2020	A*	`conf`	Coresets for Clustering in Graphs of Bounded Treewidth. ICML Daniel N. Baker, Vladimir Braverman, Lingxiao Huang, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu
2020	A*	`conf`	Cut-Equivalent Trees are Optimal for Min-Cut Queries. FOCS Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
2020	J	`jnl`	Cut-Equivalent Trees are Optimal for Min-Cut Queries. CoRR Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
2020	J	`jnl`	Faster Algorithms for Orienteering and k-TSP. CoRR Lee-Ad Gottlieb, Robert Krauthgamer, Havana Rika
2020	A*	`conf`	Labelings vs. Embeddings: On Distributed Representations of Distances. SODA Arnold Filtser, Lee-Ad Gottlieb, Robert Krauthgamer
2020	J	`jnl`	Near-Optimal Entrywise Sampling of Numerically Sparse Matrices. CoRR Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, Shay Sapir
2020	A*	`conf`	New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs. SODA Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
2020	J	`jnl`	Refined Vertex Sparsifiers of Planar Graphs. SIAM J. Discret. Math. Robert Krauthgamer, Havana Rika
2020	A*	`conf`	Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension. ICML Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, Roi Sinoff
2020	A*	`conf`	Sketching Graphs and Combinatorial Optimization (Invited Talk). ICALP Robert Krauthgamer
2020	J	`jnl`	Streaming Algorithms for Geometric Steiner Forest. CoRR Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý
2020	J	`jnl`	Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs. CoRR Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
2020	J	`jnl`	Towards Tight Bounds for Spectral Sparsification of Hypergraphs. CoRR Michael Kapralov, Robert Krauthgamer, Jakab Tardos, Yuichi Yoshida
2019	J	`jnl`	Almost-Smooth Histograms and Sliding-Window Graph Algorithms. CoRR Robert Krauthgamer, David Reitblat
2019	J	`jnl`	Coresets for Clustering in Graphs of Bounded Treewidth. CoRR Vladimir Braverman, Lingxiao Huang, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu
2019	A*	`conf`	Coresets for Ordered Weighted Clustering. ICML Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu
2019	J	`jnl`	Coresets for Ordered Weighted Clustering. CoRR Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu
2019	A*	`conf`	Faster Algorithms for All-Pairs Bounded Min-Cuts. ICALP Amir Abboud, Loukas Georgiadis, Giuseppe F. Italiano, Robert Krauthgamer, Nikos Parotsidis, Ohad Trabelsi, Przemyslaw Uznanski, Daniel Wolleb-Graf
2019	A*	`conf`	Flow-Cut Gaps and Face Covers in Planar Graphs. SODA Robert Krauthgamer, James R. Lee, Havana Rika
2019	J	`jnl`	Labelings vs. Embeddings: On Distributed Representations of Distances. CoRR Arnold Filtser, Lee-Ad Gottlieb, Robert Krauthgamer
2019	J	`jnl`	New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs. CoRR Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
2019	A	`conf`	On Solving Linear Systems in Sublinear Time. ITCS Alexandr Andoni, Robert Krauthgamer, Yosef Pogrow
2019	—	`conf`	Relaxed Voronoi: A Simple Framework for Terminal-Clustering Problems. SOSA Arnold Filtser, Robert Krauthgamer, Ohad Trabelsi
2019	J	`jnl`	Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension. CoRR Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, Roi Sinoff
2019	—	`conf`	Sketching Graphs and Combinatorial Optimization (Invited Talk). FSTTCS Robert Krauthgamer
2019	A*	`conf`	Sublinear Algorithms for Gap Edit Distance. FOCS Elazar Goldenberg, Robert Krauthgamer, Barna Saha
2019	J	`jnl`	Sublinear Algorithms for Gap Edit Distance. CoRR Elazar Goldenberg, Robert Krauthgamer, Barna Saha
2019	A	`conf`	The Set Cover Conjecture and Subgraph Isomorphism with a Tree Pattern. STACS Robert Krauthgamer, Ohad Trabelsi
2018	J	`jnl`	3rd Highlights of Algorithms (HALG 2018). SIGACT News Artur Czumaj, Robert Krauthgamer
2018	J	`jnl`	Batch Sparse Recovery, or How to Leverage the Average Sparsity. CoRR Alexandr Andoni, Lior Kamma, Robert Krauthgamer, Eric Price
2018	J	`jnl`	Conditional Lower Bounds for All-Pairs Max-Flow. ACM Trans. Algorithms Robert Krauthgamer, Ohad Trabelsi
2018	J	`jnl`	Faster Algorithms for All-Pairs Bounded Min-Cuts. CoRR Amir Abboud, Loukas Georgiadis, Daniel Graf, Giuseppe F. Italiano, Robert Krauthgamer, Nikos Parotsidis, Ohad Trabelsi, Przemyslaw Uznanski
2018	J	`jnl`	Flow-Cut Gaps and Face Covers in Planar Graphs. CoRR Robert Krauthgamer, James R. Lee, Havana Rika
2018	A*	`conf`	Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order. ICML Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Yi Li, David P. Woodruff, Lin F. Yang
2018	J	`jnl`	Noisy Voronoi: a Simple Framework for Terminal-Clustering Problems. CoRR Arnold Filtser, Robert Krauthgamer, Ohad Trabelsi
2018	J	`jnl`	On Solving Linear Systems in Sublinear Time. CoRR Alexandr Andoni, Robert Krauthgamer, Yosef Pogrow
2018	J	`jnl`	Report on HALG 2018. Bull. EATCS Artur Czumaj, Robert Krauthgamer
2018	J	`jnl`	Sketching and Embedding are Equivalent for Norms. SIAM J. Comput. Alexandr Andoni, Robert Krauthgamer, Ilya P. Razenshteyn
2018	J	`jnl`	Universal Streaming of Subset Norms. CoRR Vladimir Braverman, Robert Krauthgamer, Lin F. Yang
2017	J	`jnl`	Conditional Lower Bound for Subgraph Isomorphism with a Tree Pattern. CoRR Robert Krauthgamer, Ohad Trabelsi
2017	A*	`conf`	Conditional Lower Bounds for All-Pairs Max-Flow. ICALP Robert Krauthgamer, Ohad Trabelsi
2017	J	`jnl`	Conditional Lower Bounds for All-Pairs Max-Flow. CoRR Robert Krauthgamer, Ohad Trabelsi
2017	J	`jnl`	Efficient Regression in Metric Spaces via Approximate Lipschitz Extension. IEEE Trans. Inf. Theory Lee-Ad Gottlieb, Aryeh Kontorovich, Robert Krauthgamer
2017	J	`jnl`	Local reconstruction of low-rank matrices and subspaces. Random Struct. Algorithms Roee David, Elazar Goldenberg, Robert Krauthgamer
2017	J	`jnl`	Metric Decompositions of Path-Separable Graphs. Algorithmica Lior Kamma, Robert Krauthgamer
2017	J	`jnl`	Refined Vertex Sparsifiers of Planar Graphs. CoRR Robert Krauthgamer, Inbal Rika
2017	J	`jnl`	Revisiting the Set Cover Conjecture. CoRR Robert Krauthgamer, Ohad Trabelsi
2017	J	`jnl`	Sparsification of Two-Variable Valued Constraint Satisfaction Problems. SIAM J. Discret. Math. Arnold Filtser, Robert Krauthgamer
2017	A*	`conf`	Streaming symmetric norms via measure concentration. STOC Jaroslaw Blasiok, Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Lin F. Yang
2016	J	`jnl`	Adaptive metric dimensionality reduction. Theor. Comput. Sci. Lee-Ad Gottlieb, Aryeh Kontorovich, Robert Krauthgamer
2016	J	`jnl`	Cheeger-Type Approximation for Sparsest ACM Trans. Algorithms Robert Krauthgamer, Tal Wagner
2016	B	`conf`	Color-Distance Oracles and Snippets. CPM Tsvi Kopelowitz, Robert Krauthgamer
2016	—	`ch.`	Minimum Bisection. Encyclopedia of Algorithms Robert Krauthgamer
2016	A	`conf`	On Sketching Quadratic Forms. ITCS Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, Qin Zhang
2016	A*	`ed.`	Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016 SODA Robert Krauthgamer
2016	J	`jnl`	Sketches for Matrix Norms: Faster, Smaller and More General. CoRR Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Lin F. Yang
2016	J	`jnl`	The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme. SIAM J. Comput. Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer
2016	B	`conf`	Tight Bounds for Gomory-Hu-like Cut Counting. WG Rajesh Chitnis, Lior Kamma, Robert Krauthgamer
2015	J	`jnl`	A Nonlinear Approach to Dimension Reduction. Discret. Comput. Geom. Lee-Ad Gottlieb, Robert Krauthgamer
2015	—	`conf`	Approximate Nearest Neighbor Search in Metrics of Planar Graphs. APPROX-RANDOM Ittai Abraham, Shiri Chechik, Robert Krauthgamer, Udi Wieder
2015	J	`jnl`	Cutting Corners Cheaply, or How to Remove Steiner Points. SIAM J. Comput. Lior Kamma, Robert Krauthgamer, Huy L. Nguyen
2015	J	`jnl`	Local Reconstruction of Low-Rank Matrices and Subspaces. Electron. Colloquium Comput. Complex. Roee David, Elazar Goldenberg, Robert Krauthgamer
2015	J	`jnl`	Metric Decompositions of Path-Separable Graphs. CoRR Lior Kamma, Robert Krauthgamer
2015	J	`jnl`	On Sketching Quadratic Forms. CoRR Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, Qin Zhang
2015	A	`conf`	Sketching Cuts in Graphs and Hypergraphs. ITCS Dmitry Kogan, Robert Krauthgamer
2015	A*	`conf`	Sketching and Embedding are Equivalent for Norms. STOC Alexandr Andoni, Robert Krauthgamer, Ilya P. Razenshteyn
2015	J	`jnl`	Sparsification of Two-Variable Valued CSPs. CoRR Arnold Filtser, Robert Krauthgamer
2015	J	`jnl`	Streaming Symmetric Norms via Measure Concentration. CoRR Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Lin F. Yang
2015	J	`jnl`	Tight Bounds for Gomory-Hu-like Cut Counting. CoRR Rajesh Chitnis, Lior Kamma, Robert Krauthgamer
2015	—	`conf`	Towards Resistance Sparsifiers. APPROX-RANDOM Michael Dinitz, Robert Krauthgamer, Tal Wagner
2015	J	`jnl`	Towards Resistance Sparsifiers. CoRR Michael Dinitz, Robert Krauthgamer, Tal Wagner
2014	J	`jnl`	Cheeger-type approximation for sparsest $st$-cut. CoRR Robert Krauthgamer, Tal Wagner
2014	A*	`conf`	Cutting corners cheaply, or how to remove Steiner points. SODA Lior Kamma, Robert Krauthgamer, Huy L. Nguyen
2014	J	`jnl`	Efficient Classification for Metric Data. IEEE Trans. Inf. Theory Lee-Ad Gottlieb, Aryeh Kontorovich, Robert Krauthgamer
2014	J	`jnl`	Min-Max Graph Partitioning and Small Set Expansion. SIAM J. Comput. Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz
2014	B	`conf`	Multiply Balanced k -Partitioning. LATIN Amihood Amir, Jessica Ficler, Robert Krauthgamer, Liam Roditty, Oren Sar Shalom
2014	A*	`conf`	Non-Uniform Graph Partitioning. SODA Robert Krauthgamer, Joseph Naor, Roy Schwartz, Kunal Talwar
2014	—	`conf`	Orienting Fully Dynamic Graphs with Worst-Case Time Bounds. ICALP (2) Tsvi Kopelowitz, Robert Krauthgamer, Ely Porat, Shay Solomon
2014	J	`jnl`	Preserving Terminal Distances Using Minors. SIAM J. Discret. Math. Robert Krauthgamer, Huy L. Nguyen, Tamar Zondiner
2014	J	`jnl`	Sketching Cuts in Graphs and Hypergraphs. CoRR Dmitry Kogan, Robert Krauthgamer
2014	J	`jnl`	Sketching and Embedding are Equivalent for Norms. CoRR Alexandr Andoni, Robert Krauthgamer, Ilya P. Razenshteyn
2014	A*	`conf`	Spectral Approaches to Nearest Neighbor Search. FOCS Amirali Abdullah, Alexandr Andoni, Ravindran Kannan, Robert Krauthgamer
2014	J	`jnl`	Spectral Approaches to Nearest Neighbor Search. CoRR Amirali Abdullah, Alexandr Andoni, Ravindran Kannan, Robert Krauthgamer
2014	J	`jnl`	The Sketching Complexity of Graph Cuts. CoRR Alexandr Andoni, Robert Krauthgamer, David P. Woodruff
2014	A*	`conf`	Towards (1 + SODA Alexandr Andoni, Anupam Gupta, Robert Krauthgamer
2014	J	`jnl`	Vertex Sparsifiers: New Results from Old Techniques. SIAM J. Comput. Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Räcke, Inbal Talgam-Cohen, Kunal Talwar
2013	J	`jnl`	Adaptive Metric Dimensionality Reduction CoRR Lee-Ad Gottlieb, Aryeh Kontorovich, Robert Krauthgamer
2013	B	`conf`	Adaptive Metric Dimensionality Reduction. ALT Lee-Ad Gottlieb, Aryeh Kontorovich, Robert Krauthgamer
2013	J	`jnl`	Cutting corners cheaply, or how to remove Steiner points CoRR Lior Kamma, Robert Krauthgamer, Huy L. Nguyen
2013	C	`conf`	Efficient Approximation of Edit Distance. SPIRE Robert Krauthgamer
2013	J	`jnl`	Efficient Classification for Metric Data. CoRR Lee-Ad Gottlieb, Aryeh Kontorovich, Robert Krauthgamer
2013	—	`conf`	Efficient Regression in Metric Spaces via Approximate Lipschitz Extension. SIMBAD Lee-Ad Gottlieb, Aryeh Kontorovich, Robert Krauthgamer
2013	A*	`conf`	Mimicking Networks and Succinct Representations of Terminal Cuts. SODA Robert Krauthgamer, Inbal Rika
2013	J	`jnl`	Orienting Fully Dynamic Graphs with Worst-Case Time Bounds. CoRR Tsvi Kopelowitz, Robert Krauthgamer, Ely Porat, Shay Solomon
2013	J	`jnl`	Proximity Algorithms for Nearly Doubling Spaces. SIAM J. Discret. Math. Lee-Ad Gottlieb, Robert Krauthgamer
2013	J	`jnl`	Towards (1+ε)-Approximate Flow Sparsifiers. CoRR Alexandr Andoni, Anupam Gupta, Robert Krauthgamer
2012	J	`jnl`	Everywhere-Sparse Spanners via Dense Subgraphs CoRR Eden Chlamtac, Michael Dinitz, Robert Krauthgamer
2012	A*	`conf`	Everywhere-Sparse Spanners via Dense Subgraphs. FOCS Eden Chlamtac, Michael Dinitz, Robert Krauthgamer
2012	J	`jnl`	Faster Clustering via Preprocessing CoRR Tsvi Kopelowitz, Robert Krauthgamer
2012	J	`jnl`	Mimicking Networks and Succinct Representations of Terminal Cuts CoRR Robert Krauthgamer, Inbal Rika
2012	—	`conf`	Preserving Terminal Distances Using Minors. ICALP (1) Robert Krauthgamer, Tamar Zondiner
2012	J	`jnl`	Preserving Terminal Distances using Minors CoRR Robert Krauthgamer, Tamar Zondiner
2012	J	`jnl`	The smoothed complexity of edit distance. ACM Trans. Algorithms Alexandr Andoni, Robert Krauthgamer
2012	A*	`conf`	The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. STOC Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer
2011	A*	`conf`	A Nonlinear Approach to Dimension Reduction. SODA Lee-Ad Gottlieb, Robert Krauthgamer
2011	A*	`conf`	Directed spanners via flow-based linear programs. STOC Michael Dinitz, Robert Krauthgamer
2011	J	`jnl`	Efficient Regression in Metric Spaces via Approximate Lipschitz Extension CoRR Lee-Ad Gottlieb, Aryeh Kontorovich, Robert Krauthgamer
2011	J	`jnl`	Fault-Tolerant Spanners: Better and Simpler CoRR Michael Dinitz, Robert Krauthgamer
2011	A*	`conf`	Fault-tolerant spanners: better and simpler. PODC Michael Dinitz, Robert Krauthgamer
2011	J	`jnl`	How Hard Is It to Approximate the Best Nash Equilibrium? SIAM J. Comput. Elad Hazan, Robert Krauthgamer
2011	J	`jnl`	Metric Clustering via Consistent Labeling. Theory Comput. Robert Krauthgamer, Tim Roughgarden
2011	J	`jnl`	Min-Max Graph Partitioning and Small Set Expansion CoRR Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz
2011	A*	`conf`	Min-max Graph Partitioning and Small Set Expansion. FOCS Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz
2011	J	`jnl`	Pricing commodities. Theor. Comput. Sci. Robert Krauthgamer, Aranyak Mehta, Atri Rudra
2011	A*	`conf`	Streaming Algorithms via Precision Sampling. FOCS Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
2011	J	`jnl`	The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme CoRR Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer
2010	J	`jnl`	Approximating Sparsest Cut in Graphs of Bounded Treewidth CoRR Eden Chlamtac, Robert Krauthgamer, Prasad Raghavendra
2010	—	`conf`	Approximating Sparsest Cut in Graphs of Bounded Treewidth. APPROX-RANDOM Eden Chlamtac, Robert Krauthgamer, Prasad Raghavendra
2010	J	`jnl`	Directed Spanners via Flow-Based Linear Programs CoRR Michael Dinitz, Robert Krauthgamer
2010	A*	`conf`	Efficient Classification for Metric Data. COLT Lee-Ad Gottlieb, Leonid Kontorovich, Robert Krauthgamer
2010	J	`jnl`	Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity CoRR Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
2010	A*	`conf`	Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. FOCS Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
2010	—	`ch.`	Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. Property Testing Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
2010	—	`conf`	Proximity Algorithms for Nearly-Doubling Spaces. APPROX-RANDOM Lee-Ad Gottlieb, Robert Krauthgamer
2010	J	`jnl`	Streaming Algorithms from Precision Sampling CoRR Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
2010	J	`jnl`	The Computational Hardness of Estimating Edit Distance. SIAM J. Comput. Alexandr Andoni, Robert Krauthgamer
2010	J	`jnl`	Vertex Sparsifiers: New Results from Old Techniques CoRR Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Räcke, Inbal Talgam-Cohen, Kunal Talwar
2010	—	`conf`	Vertex Sparsifiers: New Results from Old Techniques. APPROX-RANDOM Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Räcke, Inbal Talgam-Cohen, Kunal Talwar
2009	J	`jnl`	A Nonlinear Approach to Dimension Reduction CoRR Lee-Ad Gottlieb, Robert Krauthgamer
2009	A*	`conf`	Approximate line nearest neighbor in high dimensions. SODA Alexandr Andoni, Piotr Indyk, Robert Krauthgamer, Huy L. Nguyen
2009	A*	`conf`	How hard is it to approximate the best Nash equilibrium? SODA Elad Hazan, Robert Krauthgamer
2009	J	`jnl`	Improved Lower Bounds for Embeddings intoL SIAM J. Comput. Robert Krauthgamer, Yuval Rabani
2009	A*	`conf`	Overcoming the SODA Alexandr Andoni, Piotr Indyk, Robert Krauthgamer
2009	A*	`conf`	Partitioning graphs into balanced components. SODA Robert Krauthgamer, Joseph Naor, Roy Schwartz
2008	A*	`conf`	Earth mover distance over high-dimensional spaces. SODA Alexandr Andoni, Piotr Indyk, Robert Krauthgamer
2008	A*	`conf`	Greedy List Intersection. ICDE Robert Krauthgamer, Aranyak Mehta, Vijayshankar Raman, Atri Rudra
2008	A*	`conf`	Metric clustering via consistent labeling. SODA Robert Krauthgamer, Tim Roughgarden
2008	—	`ch.`	Minimum Bisection. Encyclopedia of Algorithms Robert Krauthgamer
2008	—	`conf`	The Smoothed Complexity of Edit Distance. ICALP (1) Alexandr Andoni, Robert Krauthgamer
2007	J	`jnl`	Earth Mover Distance over High-Dimensional Spaces. Electron. Colloquium Comput. Complex. Alexandr Andoni, Piotr Indyk, Robert Krauthgamer
2007	A*	`conf`	Estimating the sortedness of a data stream. SODA Parikshit Gopalan, T. S. Jayram, Robert Krauthgamer, Ravi Kumar
2007	J	`jnl`	Integrality Ratio for Group Steiner Trees and Directed Steiner Trees. SIAM J. Comput. Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang
2007	B	`conf`	On triangulation of simple networks. SPAA Robert Krauthgamer
2007	B	`conf`	Pricing Commodities, or How to Sell When Buyers Have Restricted Valuations. WAOA Robert Krauthgamer, Aranyak Mehta, Atri Rudra
2007	A*	`conf`	The Computational Hardness of Estimating Edit Distance [Extended Abstract]. FOCS Alexandr Andoni, Robert Krauthgamer
2007	J	`jnl`	The intrinsic dimensionality of graphs. Comb. Robert Krauthgamer, James R. Lee
2006	J	`jnl`	A Polylogarithmic Approximation of the Minimum Bisection. SIAM Rev. Robert Krauthgamer, Uriel Feige
2006	A*	`conf`	Algorithms on negatively curved spaces. FOCS Robert Krauthgamer, James R. Lee
2006	J	`jnl`	Embedding the Ulam metric into Theory Comput. Moses Charikar, Robert Krauthgamer
2006	A*	`conf`	Improved lower bounds for embeddings into SODA Robert Krauthgamer, Yuval Rabani
2006	J	`jnl`	On the Hardness of Approximating Multicut and Sparsest-Cut. Comput. Complex. Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, D. Sivakumar
2005	J	`jnl`	Asymmetric J. ACM Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Robert Krauthgamer, Joseph Naor
2005	A	`conf`	On the Hardness of Approximating Multicut and Sparsest-Cut. CCC Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, D. Sivakumar
2005	J	`jnl`	The black-box complexity of nearest-neighbor search. Theor. Comput. Sci. Robert Krauthgamer, James R. Lee
2004	A*	`conf`	Approximate classification via earthmover metrics. SODA Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, Éva Tardos
2004	A*	`conf`	Approximating Edit Distance Efficiently. FOCS Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer, Ravi Kumar
2004	J	`jnl`	Hardness of Approximation for Vertex-Connectivity Network Design Problems. SIAM J. Comput. Guy Kortsarz, Robert Krauthgamer, James R. Lee
2004	A*	`conf`	Measured Descent: A New Embedding Method for Finite Metrics. FOCS Robert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor
2004	J	`jnl`	Measured descent: A new embedding method for finite metrics CoRR Robert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor
2004	J	`jnl`	Metric Embeddings--Beyond One-Dimensional Distortion. Discret. Comput. Geom. Robert Krauthgamer, Nathan Linial, Avner Magen
2004	A*	`conf`	Navigating nets: simple algorithms for proximity search. SODA Robert Krauthgamer, James R. Lee
2004	B	`conf`	Object location in realistic networks. SPAA Kirsten Hildrum, Robert Krauthgamer, John Kubiatowicz
2004	A*	`conf`	The Black-Box Complexity of Nearest Neighbor Search. ICALP Robert Krauthgamer, James R. Lee
2004	—	`conf`	The Sketching Complexity of Pattern Matching. APPROX-RANDOM Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer, Ravi Kumar
2003	A*	`conf`	Bounded Geometries, Fractals, and Low-Distortion Embeddings. FOCS Anupam Gupta, Robert Krauthgamer, James R. Lee
2003	A*	`conf`	Constant factor approximation of vertex-cuts in planar graphs. STOC Eyal Amir, Robert Krauthgamer, Satish Rao
2003	—	`conf`	Detecting protein sequence conservation via metric embeddings. ISMB (Supplement of Bioinformatics) Eran Halperin, Jeremy Buhler, Richard M. Karp, Robert Krauthgamer, Ben Westover
2003	A*	`conf`	Integrality ratio for group Steiner trees and directed steiner trees. SODA Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang
2003	J	`jnl`	On Cutting a Few Vertices from a Graph. Discret. Appl. Math. Uriel Feige, Robert Krauthgamer, Kobbi Nissim
2003	A*	`conf`	Polylogarithmic inapproximability. STOC Eran Halperin, Robert Krauthgamer
2003	A*	`conf`	Property testing of data dimensionality. SODA Robert Krauthgamer, Ori Sasson
2003	J	`jnl`	The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set. SIAM J. Comput. Uriel Feige, Robert Krauthgamer
2003	A*	`conf`	The intrinsic dimensionality of graphs. STOC Robert Krauthgamer, James R. Lee
2003	J	`jnl`	Tight lower bounds for the asymmetric k-center problem Electron. Colloquium Comput. Complex. Eran Halperin, Guy Kortsarz, Robert Krauthgamer
2002	J	`jnl`	A Polylogarithmic Approximation of the Minimum Bisection. SIAM J. Comput. Uriel Feige, Robert Krauthgamer
2002	—	`conf`	Hardness of Approximation for Vertex-Connectivity Network-Design Problems. APPROX Guy Kortsarz, Robert Krauthgamer, James R. Lee
2001	J	`jnl`	On Approximating the Achromatic Number. SIAM J. Discret. Math. Guy Kortsarz, Robert Krauthgamer
2001	A*	`conf`	On approximating the achromatic number. SODA Guy Kortsarz, Robert Krauthgamer
2001	A*	`conf`	Online server allocation in a server farm via benefit task systems. STOC T. S. Jayram, Tracy Kimbrel, Robert Krauthgamer, Baruch Schieber, Maxim Sviridenko
2001	A*	`conf`	Private approximation of NP-hard functions. STOC Shai Halevi, Robert Krauthgamer, Eyal Kushilevitz, Kobbi Nissim
2000	A*	`conf`	A polylogarithmic approximation of the minimum bisection. FOCS Uriel Feige, Robert Krauthgamer
2000	A*	`conf`	Approximating the minimum bisection size (extended abstract). STOC Uriel Feige, Robert Krauthgamer, Kobbi Nissim
2000	J	`jnl`	Finding and certifying a large hidden clique in a semirandom graph. Random Struct. Algorithms Uriel Feige, Robert Krauthgamer
2000	A*	`conf`	Improved classification via connectivity information. SODA Andrei Z. Broder, Robert Krauthgamer, Michael Mitzenmacher
2000	J	`jnl`	Networks on Which Hot-Potato Routing Does Not Livelock. Distributed Comput. Uriel Feige, Robert Krauthgamer
1997	—	`conf`	Stereoscopic families of permutations, and their applications. ISTCS Uriel Feige, Robert Krauthgamer