default search action
Robert Krauthgamer
Person information
- affiliation: Weizmann Institute of Science, Israel
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
- [j49]Arnold Filtser
, Lee-Ad Gottlieb, Robert Krauthgamer:
Labelings vs. Embeddings: On Distributed and Prioritized Representations of Distances. Discret. Comput. Geom. 71(3): 849-871 (2024) - [j48]Shaofeng H.-C. Jiang
Coresets for kernel clustering. Mach. Learn. 113(8): 5891-5906 (2024) - [j47]Artur Czumaj
Streaming Algorithms for Geometric Steiner Forest. ACM Trans. Algorithms 20(4): 28:1-28:38 (2024) - [c109]Chen Amiraz, Robert Krauthgamer, Boaz Nadler:
Recovery Guarantees for Distributed-OMP. AISTATS 2024: 802-810 - [c108]Shaofeng H.-C. Jiang, Robert Krauthgamer, Shay Sapir
Moderate Dimension Reduction for k-Center Clustering. SoCG 2024: 64:1-64:16 - [c107]Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý:
Fully-Scalable MPC Algorithms for Clustering in High Dimension. ICALP 2024: 50:1-50:20 - [c106]Yotam Kenneth, Robert Krauthgamer:
Cut Sparsification and Succinct Representation of Submodular Hypergraphs. ICALP 2024: 97:1-97:17 - 2023
- [j46]Robert Krauthgamer, Shay Sapir
Comparison of Matrix Norm Sparsification. Algorithmica 85(12): 3957-3972 (2023) - [c105]Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, Shay Sapir
Lower Bounds for Pseudo-Deterministic Counting in a Stream. ICALP 2023: 30:1-30:14 - [c104]Diptarka Chakraborty, Debarati Das, Robert Krauthgamer:
Clustering Permutations: New Techniques with Streaming Applications. ITCS 2023: 31:1-31:24 - [c103]Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha:
An Algorithmic Bridge Between Hamming and Levenshtein Distances. ITCS 2023: 58:1-58:23 - [c102]Robert Krauthgamer, Ron Mosenzon:
Exact Flow Sparsification Requires Unbounded Size. SODA 2023: 2354-2367 - [c101]Xiaoyu Chen, Shaofeng H.-C. Jiang, Robert Krauthgamer:
Streaming Euclidean Max-Cut: Dimension vs Data Reduction. STOC 2023: 170-182 - [i85]Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, Shay Sapir:
Lower Bounds for Pseudo-Deterministic Counting in a Stream. CoRR abs/2303.16287 (2023) - [i84]Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý:
Fully Scalable MPC Algorithms for Clustering in High Dimension. CoRR abs/2307.07848 (2023) - [i83]Yotam Kenneth, Robert Krauthgamer:
Cut Sparsification and Succinct Representation of Submodular Hypergraphs. CoRR abs/2307.09110 (2023) - [i82]Shaofeng H.-C. Jiang, Robert Krauthgamer, Shay Sapir
Moderate Dimension Reduction for k-Center Clustering. CoRR abs/2312.01391 (2023) - 2022
- [j45]Robert Krauthgamer, David Reitblat
Almost-Smooth Histograms and Sliding-Window Graph Algorithms. Algorithmica 84(10): 2926-2953 (2022) - [j44]Robert Krauthgamer, Shay Sapir
Smoothness of Schatten norms and sliding-window matrix streams. Inf. Process. Lett. 177: 106254 (2022) - [j43]Lee-Ad Gottlieb, Robert Krauthgamer, Havana Rika
Faster algorithms for orienteering and k-TSP. Theor. Comput. Sci. 914: 73-83 (2022) - [j42]Vladimir Braverman, Robert Krauthgamer
Universal Streaming of Subset Norms. Adv. Math. Commun. 18: 1-32 (2022) - [c100]Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer
Streaming Facility Location in High Dimension via Geometric Hashing. FOCS 2022: 450-461 - [c99]Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer
The Power of Uniform Sampling for Coresets. FOCS 2022: 462-473 - [c98]Elazar Goldenberg, Tomasz Kociumaka
Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal. FOCS 2022: 674-685 - [c97]Amir Abboud, Robert Krauthgamer
Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time. FOCS 2022: 884-895 - [c96]Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý
Streaming Algorithms for Geometric Steiner Forest. ICALP 2022: 47:1-47:20 - [c95]Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
Friendly Cut Sparsifiers and Faster Gomory-Hu Trees. SODA 2022: 3630-3649 - [c94]Hsien-Chih Chang, Robert Krauthgamer
Almost-linear ε-emulators for planar graphs. STOC 2022: 1311-1324 - [i81]Robert Krauthgamer, Shay Sapir:
Comparison of Matrix Norm Sparsification. CoRR abs/2201.12874 (2022) - [i80]Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý
Streaming Facility Location in High Dimension via New Geometric Hashing. CoRR abs/2204.02095 (2022) - [i79]Hsien-Chih Chang, Robert Krauthgamer, Zihan Tan:
Near-Linear ε-Emulators for Planar Graphs. CoRR abs/2206.10681 (2022) - [i78]Itai Boneh, Robert Krauthgamer:
Optimal Vertex-Cut Sparsification of Quasi-Bipartite Graphs. CoRR abs/2207.01459 (2022) - [i77]Robert Krauthgamer, Ron Mosenzon:
Exact Flow Sparsification Requires Unbounded Size. CoRR abs/2207.07363 (2022) - [i76]Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, Xuan Wu:
The Power of Uniform Sampling for Coresets. CoRR abs/2209.01901 (2022) - [i75]Chen Amiraz, Robert Krauthgamer, Boaz Nadler
Distributed Sparse Linear Regression with Sublinear Communication. CoRR abs/2209.07230 (2022) - [i74]Yu Chen, Shaofeng H.-C. Jiang, Robert Krauthgamer:
Streaming Euclidean Max-Cut: Dimension vs Data Reduction. CoRR abs/2211.05293 (2022) - [i73]Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha:
An Algorithmic Bridge Between Hamming and Levenshtein Distances. CoRR abs/2211.12496 (2022) - [i72]Diptarka Chakraborty, Debarati Das, Robert Krauthgamer:
Clustering Permutations: New Techniques with Streaming Applications. CoRR abs/2212.01821 (2022) - 2021
- [j41]Amir Abboud, Robert Krauthgamer
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs. Adv. Math. Commun. 17: 1-27 (2021) - [c93]Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, Shay Sapir:
Near-Optimal Entrywise Sampling of Numerically Sparse Matrices. COLT 2021: 759-773 - [c92]Amir Abboud, Robert Krauthgamer
APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time. FOCS 2021: 1135-1146 - [c91]Michael Kapralov
Spectral Hypergraph Sparsifiers of Nearly Linear Size. FOCS 2021: 1159-1170 - [c90]Diptarka Chakraborty, Debarati Das, Robert Krauthgamer:
Approximate Trace Reconstruction via Median String (In Average-Case). FSTTCS 2021: 11:1-11:23 - [c89]Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu:
Coresets for Clustering with Missing Values. NeurIPS 2021: 17360-17372 - [c88]Diptarka Chakraborty, Debarati Das, Robert Krauthgamer:
Approximating the Median under the Ulam Metric. SODA 2021: 761-775 - [c87]Vladimir Braverman, Shaofeng H.-C. Jiang
Coresets for Clustering in Excluded-minor Graphs and Beyond. SODA 2021: 2679-2696 - [c86]Michael Kapralov
Towards tight bounds for spectral sparsification of hypergraphs. STOC 2021: 598-611 - [c85]Amir Abboud, Robert Krauthgamer
Subcubic algorithms for Gomory-Hu tree in unweighted graphs. STOC 2021: 1725-1737 - [i71]Chen Amiraz, Robert Krauthgamer, Boaz Nadler:
Sparse Normal Means Estimation with Sublinear Communication. CoRR abs/2102.03060 (2021) - [i70]Robert Krauthgamer, Shay Sapir:
Smoothness of Schatten Norms and Sliding-Window Matrix Streams. CoRR abs/2103.08211 (2021) - [i69]Michael Kapralov, Robert Krauthgamer, Jakab Tardos, Yuichi Yoshida:
Spectral Hypergraph Sparsifiers of Nearly Linear Size. CoRR abs/2106.02353 (2021) - [i68]Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time. CoRR abs/2106.02981 (2021) - [i67]Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu:
Coresets for Clustering with Missing Values. CoRR abs/2106.16112 (2021) - [i66]Diptarka Chakraborty, Debarati Das, Robert Krauthgamer:
Approximate Trace Reconstruction via Median String (in Average-Case). CoRR abs/2107.09497 (2021) - [i65]Shaofeng H.-C. Jiang, Robert Krauthgamer, Jianing Lou, Yubo Zhang:
Coresets for Kernel Clustering. CoRR abs/2110.02898 (2021) - [i64]Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
Friendly Cut Sparsifiers and Faster Gomory-Hu Trees. CoRR abs/2110.15891 (2021) - [i63]Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak
Gomory-Hu Tree in Subcubic Time. CoRR abs/2111.04958 (2021) - [i62]Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha:
Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal. CoRR abs/2111.12706 (2021) - [i61]Lior Kalman, Robert Krauthgamer:
Flow Metrics on Graphs. CoRR abs/2112.06916 (2021) - 2020
- [j40]Robert Krauthgamer, Havana Rika
Refined Vertex Sparsifiers of Planar Graphs. SIAM J. Discret. Math. 34(1): 101-129 (2020) - [c84]Amir Abboud, Robert Krauthgamer
Cut-Equivalent Trees are Optimal for Min-Cut Queries. FOCS 2020: 105-118 - [c83]Robert Krauthgamer:
Sketching Graphs and Combinatorial Optimization (Invited Talk). ICALP 2020: 2:1-2:1 - [c82]Daniel N. Baker, Vladimir Braverman, Lingxiao Huang, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu:
Coresets for Clustering in Graphs of Bounded Treewidth. ICML 2020: 569-579 - [c81]Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, Roi Sinoff:
Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension. ICML 2020: 1100-1110 - [c80]Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs. SODA 2020: 48-61 - [c79]Arnold Filtser, Lee-Ad Gottlieb, Robert Krauthgamer:
Labelings vs. Embeddings: On Distributed Representations of Distances. SODA 2020: 1063-1075 - [i60]Lee-Ad Gottlieb, Robert Krauthgamer, Havana Rika:
Faster Algorithms for Orienteering and k-TSP. CoRR abs/2002.07727 (2020) - [i59]Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu:
Coresets for Clustering in Excluded-minor Graphs and Beyond. CoRR abs/2004.07718 (2020) - [i58]Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
Cut-Equivalent Trees are Optimal for Min-Cut Queries. CoRR abs/2009.06090 (2020) - [i57]Diptarka Chakraborty, Debarati Das, Robert Krauthgamer:
Approximating the Median under the Ulam Metric. CoRR abs/2011.00868 (2020) - [i56]Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, Shay Sapir:
Near-Optimal Entrywise Sampling of Numerically Sparse Matrices. CoRR abs/2011.01777 (2020) - [i55]Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý:
Streaming Algorithms for Geometric Steiner Forest. CoRR abs/2011.04324 (2020) - [i54]Michael Kapralov, Robert Krauthgamer, Jakab Tardos, Yuichi Yoshida:
Towards Tight Bounds for Spectral Sparsification of Hypergraphs. CoRR abs/2011.06530 (2020) - [i53]Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs. CoRR abs/2012.10281 (2020)
2010 – 2019
- 2019
- [c78]Elazar Goldenberg, Robert Krauthgamer
Sublinear Algorithms for Gap Edit Distance. FOCS 2019: 1101-1120 - [c77]Robert Krauthgamer:
Sketching Graphs and Combinatorial Optimization (Invited Talk). FSTTCS 2019: 2:1-2:1 - [c76]Amir Abboud, Loukas Georgiadis
Faster Algorithms for All-Pairs Bounded Min-Cuts. ICALP 2019: 7:1-7:15 - [c75]Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu:
Coresets for Ordered Weighted Clustering. ICML 2019: 744-753 - [c74]Alexandr Andoni, Robert Krauthgamer, Yosef Pogrow:
On Solving Linear Systems in Sublinear Time. ITCS 2019: 3:1-3:19 - [c73]Arnold Filtser, Robert Krauthgamer, Ohad Trabelsi:
Relaxed Voronoi: A Simple Framework for Terminal-Clustering Problems. SOSA 2019: 10:1-10:14 - [c72]Robert Krauthgamer, James R. Lee, Havana Rika
Flow-Cut Gaps and Face Covers in Planar Graphs. SODA 2019: 525-534 - [c71]Robert Krauthgamer, Ohad Trabelsi:
The Set Cover Conjecture and Subgraph Isomorphism with a Tree Pattern. STACS 2019: 45:1-45:15 - [i52]Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs. CoRR abs/1901.01412 (2019) - [i51]Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu:
Coresets for Ordered Weighted Clustering. CoRR abs/1903.04351 (2019) - [i50]Robert Krauthgamer, David Reitblat:
Almost-Smooth Histograms and Sliding-Window Graph Algorithms. CoRR abs/1904.07957 (2019) - [i49]Vladimir Braverman, Lingxiao Huang, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu:
Coresets for Clustering in Graphs of Bounded Treewidth. CoRR abs/1907.04733 (2019) - [i48]Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, Roi Sinoff:
Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension. CoRR abs/1907.05457 (2019) - [i47]Arnold Filtser, Lee-Ad Gottlieb, Robert Krauthgamer:
Labelings vs. Embeddings: On Distributed Representations of Distances. CoRR abs/1907.06857 (2019) - [i46]Elazar Goldenberg, Robert Krauthgamer, Barna Saha:
Sublinear Algorithms for Gap Edit Distance. CoRR abs/1910.00901 (2019) - 2018
- [j39]Artur Czumaj, Robert Krauthgamer:
Report on HALG 2018. Bull. EATCS 126 (2018) - [j38]Alexandr Andoni, Robert Krauthgamer
Sketching and Embedding are Equivalent for Norms. SIAM J. Comput. 47(3): 890-916 (2018) - [j37]Artur Czumaj, Robert Krauthgamer:
3rd Highlights of Algorithms (HALG 2018). SIGACT News 49(3): 74-77 (2018) - [j36]Robert Krauthgamer, Ohad Trabelsi:
Conditional Lower Bounds for All-Pairs Max-Flow. ACM Trans. Algorithms 14(4): 42:1-42:15 (2018) - [c70]Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Yi Li, David P. Woodruff, Lin F. Yang
Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order. ICML 2018: 648-657 - [i45]Amir Abboud, Loukas Georgiadis, Daniel Graf, Giuseppe F. Italiano, Robert Krauthgamer, Nikos Parotsidis, Ohad Trabelsi, Przemyslaw Uznanski:
Faster Algorithms for All-Pairs Bounded Min-Cuts. CoRR abs/1807.05803 (2018) - [i44]Alexandr Andoni, Lior Kamma, Robert Krauthgamer, Eric Price:
Batch Sparse Recovery, or How to Leverage the Average Sparsity. CoRR abs/1807.08478 (2018) - [i43]Arnold Filtser, Robert Krauthgamer, Ohad Trabelsi:
Noisy Voronoi: a Simple Framework for Terminal-Clustering Problems. CoRR abs/1809.00942 (2018) - [i42]Alexandr Andoni, Robert Krauthgamer, Yosef Pogrow:
On Solving Linear Systems in Sublinear Time. CoRR abs/1809.02995 (2018) - [i41]Robert Krauthgamer, James R. Lee, Havana Rika:
Flow-Cut Gaps and Face Covers in Planar Graphs. CoRR abs/1811.02685 (2018) - [i40]Vladimir Braverman, Robert Krauthgamer, Lin F. Yang:
Universal Streaming of Subset Norms. CoRR abs/1812.00241 (2018) - 2017
- [j35]Lior Kamma
Metric Decompositions of Path-Separable Graphs. Algorithmica 79(3): 645-653 (2017) - [j34]Roee David, Elazar Goldenberg, Robert Krauthgamer
Local reconstruction of low-rank matrices and subspaces. Random Struct. Algorithms 51(4): 607-630 (2017) - [j33]Arnold Filtser, Robert Krauthgamer:
Sparsification of Two-Variable Valued Constraint Satisfaction Problems. SIAM J. Discret. Math. 31(2): 1263-1276 (2017) - [j32]Lee-Ad Gottlieb
Efficient Regression in Metric Spaces via Approximate Lipschitz Extension. IEEE Trans. Inf. Theory 63(8): 4838-4849 (2017) - [c69]Robert Krauthgamer, Ohad Trabelsi:
Conditional Lower Bounds for All-Pairs Max-Flow. ICALP 2017: 20:1-20:13 - [c68]Jaroslaw Blasiok
Streaming symmetric norms via measure concentration. STOC 2017: 716-729 - [i39]Robert Krauthgamer, Ohad Trabelsi:
Conditional Lower Bounds for All-Pairs Max-Flow. CoRR abs/1702.05805 (2017) - [i38]Robert Krauthgamer, Inbal Rika:
Refined Vertex Sparsifiers of Planar Graphs. CoRR abs/1702.05951 (2017) - [i37]Robert Krauthgamer, Ohad Trabelsi:
Conditional Lower Bound for Subgraph Isomorphism with a Tree Pattern. CoRR abs/1708.07591 (2017) - [i36]Robert Krauthgamer, Ohad Trabelsi:
Revisiting the Set Cover Conjecture. CoRR abs/1711.08041 (2017) - 2016
- [j31]Yair Bartal, Lee-Ad Gottlieb
The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme. SIAM J. Comput. 45(4): 1563-1581 (2016) - [j30]Robert Krauthgamer, Tal Wagner:
Cheeger-Type Approximation for Sparsest st-Cut. ACM Trans. Algorithms 13(1): 14:1-14:21 (2016) - [j29]Lee-Ad Gottlieb
Adaptive metric dimensionality reduction. Theor. Comput. Sci. 620: 105-118 (2016) - [c67]Tsvi Kopelowitz, Robert Krauthgamer:
Color-Distance Oracles and Snippets. CPM 2016: 24:1-24:10 - [c66]Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin
On Sketching Quadratic Forms. ITCS 2016: 311-319 - [c65]Rajesh Chitnis
Tight Bounds for Gomory-Hu-like Cut Counting. WG 2016: 133-144 - [e1]Robert Krauthgamer:
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016. SIAM 2016, ISBN 978-1-61197-433-1 [contents] - [r2]Robert Krauthgamer:
Minimum Bisection. Encyclopedia of Algorithms 2016: 1294-1297 - [i35]Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Lin F. Yang:
Sketches for Matrix Norms: Faster, Smaller and More General. CoRR abs/1609.05885 (2016) - 2015
- [j28]Lee-Ad Gottlieb
A Nonlinear Approach to Dimension Reduction. Discret. Comput. Geom. 54(2): 291-315 (2015) - [j27]Lior Kamma, Robert Krauthgamer
Cutting Corners Cheaply, or How to Remove Steiner Points. SIAM J. Comput. 44(4): 975-995 (2015) - [c64]Ittai Abraham, Shiri Chechik, Robert Krauthgamer, Udi Wieder:
Approximate Nearest Neighbor Search in Metrics of Planar Graphs. APPROX-RANDOM 2015: 20-42 - [c63]Michael Dinitz
Towards Resistance Sparsifiers. APPROX-RANDOM 2015: 738-755 - [c62]Dmitry Kogan, Robert Krauthgamer:
Sketching Cuts in Graphs and Hypergraphs. ITCS 2015: 367-376 - [c61]Alexandr Andoni, Robert Krauthgamer
Sketching and Embedding are Equivalent for Norms. STOC 2015: 479-488 - [i34]Lior Kamma, Robert Krauthgamer:
Metric Decompositions of Path-Separable Graphs. CoRR abs/1504.07019 (2015) - [i33]Michael Dinitz, Robert Krauthgamer, Tal Wagner:
Towards Resistance Sparsifiers. CoRR abs/1506.07568 (2015) - [i32]Arnold Filtser, Robert Krauthgamer:
Sparsification of Two-Variable Valued CSPs. CoRR abs/1509.01844 (2015) - [i31]Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Lin F. Yang:
Streaming Symmetric Norms via Measure Concentration. CoRR abs/1511.01111 (2015) - [i30]Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, Qin Zhang:
On Sketching Quadratic Forms. CoRR abs/1511.06099 (2015) - [i29]Rajesh Chitnis, Lior Kamma, Robert Krauthgamer:
Tight Bounds for Gomory-Hu-like Cut Counting. CoRR abs/1511.08647 (2015) - [i28]Roee David, Elazar Goldenberg, Robert Krauthgamer:
Local Reconstruction of Low-Rank Matrices and Subspaces. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j26]Nikhil Bansal, Uriel Feige, Robert Krauthgamer
Min-Max Graph Partitioning and Small Set Expansion. SIAM J. Comput. 43(2): 872-904 (2014) - [j25]Matthias Englert, Anupam Gupta, Robert Krauthgamer
Vertex Sparsifiers: New Results from Old Techniques. SIAM J. Comput. 43(4): 1239-1262 (2014) - [j24]Robert Krauthgamer, Huy L. Nguyen, Tamar Zondiner:
Preserving Terminal Distances Using Minors. SIAM J. Discret. Math. 28(1): 127-141 (2014) - [j23]Lee-Ad Gottlieb
Efficient Classification for Metric Data. IEEE Trans. Inf. Theory 60(9): 5750-5759 (2014) - [c60]Amirali Abdullah, Alexandr Andoni, Ravindran Kannan, Robert Krauthgamer
Spectral Approaches to Nearest Neighbor Search. FOCS 2014: 581-590 - [c59]Tsvi Kopelowitz, Robert Krauthgamer
Orienting Fully Dynamic Graphs with Worst-Case Time Bounds. ICALP (2) 2014: 532-543 - [c58]Amihood Amir, Jessica Ficler, Robert Krauthgamer
Multiply Balanced k -Partitioning. LATIN 2014: 586-597 - [c57]Alexandr Andoni, Anupam Gupta, Robert Krauthgamer:
Towards (1 + ∊)-Approximate Flow Sparsifiers. SODA 2014: 279-293 - [c56]Lior Kamma, Robert Krauthgamer, Huy L. Nguyen:
Cutting corners cheaply, or how to remove Steiner points. SODA 2014: 1029-1040 - [c55]Robert Krauthgamer, Joseph Naor, Roy Schwartz, Kunal Talwar:
Non-Uniform Graph Partitioning. SODA 2014: 1229-1243 - [i27]Alexandr Andoni, Robert Krauthgamer, David P. Woodruff:
The Sketching Complexity of Graph Cuts. CoRR abs/1403.7058 (2014) - [i26]Amirali Abdullah, Alexandr Andoni, Ravindran Kannan, Robert Krauthgamer:
Spectral Approaches to Nearest Neighbor Search. CoRR abs/1408.0751 (2014) - [i25]Dmitry Kogan, Robert Krauthgamer:
Sketching Cuts in Graphs and Hypergraphs. CoRR abs/1409.2391 (2014) - [i24]Robert Krauthgamer, Tal Wagner:
Cheeger-type approximation for sparsest $st$-cut. CoRR abs/1410.3889 (2014) - [i23]Alexandr Andoni, Robert Krauthgamer, Ilya P. Razenshteyn:
Sketching and Embedding are Equivalent for Norms. CoRR abs/1411.2577 (2014) - 2013
- [j22]Lee-Ad Gottlieb
Proximity Algorithms for Nearly Doubling Spaces. SIAM J. Discret. Math. 27(4): 1759-1769 (2013) - [c54]Lee-Ad Gottlieb
Adaptive Metric Dimensionality Reduction. ALT 2013: 279-293 - [c53]Lee-Ad Gottlieb
Efficient Regression in Metric Spaces via Approximate Lipschitz Extension. SIMBAD 2013: 43-58 - [c52]Robert Krauthgamer, Inbal Rika
Mimicking Networks and Succinct Representations of Terminal Cuts. SODA 2013: 1789-1799 - [c51]Robert Krauthgamer:
Efficient Approximation of Edit Distance. SPIRE 2013: 3 - [i22]Lee-Ad Gottlieb, Aryeh Kontorovich, Robert Krauthgamer:
Adaptive Metric Dimensionality Reduction. CoRR abs/1302.2752 (2013) - [i21]Lior Kamma, Robert Krauthgamer, Huy L. Nguyen:
Cutting corners cheaply, or how to remove Steiner points. CoRR abs/1304.1449 (2013) - [i20]Lee-Ad Gottlieb, Aryeh Kontorovich, Robert Krauthgamer:
Efficient Classification for Metric Data. CoRR abs/1306.2547 (2013) - [i19]Alexandr Andoni, Anupam Gupta, Robert Krauthgamer:
Towards (1+ε)-Approximate Flow Sparsifiers. CoRR abs/1310.3252 (2013) - [i18]Tsvi Kopelowitz, Robert Krauthgamer, Ely Porat, Shay Solomon:
Orienting Fully Dynamic Graphs with Worst-Case Time Bounds. CoRR abs/1312.1382 (2013) - 2012
- [j21]Alexandr Andoni, Robert Krauthgamer:
The smoothed complexity of edit distance. ACM Trans. Algorithms 8(4): 44:1-44:25 (2012) - [c50]Eden Chlamtac, Michael Dinitz
Everywhere-Sparse Spanners via Dense Subgraphs. FOCS 2012: 758-767 - [c49]Robert Krauthgamer
Preserving Terminal Distances Using Minors. ICALP (1) 2012: 594-605 - [c48]Yair Bartal, Lee-Ad Gottlieb
The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. STOC 2012: 663-672 - [i17]Robert Krauthgamer, Tamar Zondiner:
Preserving Terminal Distances using Minors. CoRR abs/1202.5675 (2012) - [i16]Eden Chlamtac, Michael Dinitz, Robert Krauthgamer:
Everywhere-Sparse Spanners via Dense Subgraphs. CoRR abs/1205.0144 (2012) - [i15]Robert Krauthgamer, Inbal Rika:
Mimicking Networks and Succinct Representations of Terminal Cuts. CoRR abs/1207.6246 (2012) - [i14]Tsvi Kopelowitz, Robert Krauthgamer:
Faster Clustering via Preprocessing. CoRR abs/1208.5247 (2012) - 2011
- [j20]Elad Hazan
How Hard Is It to Approximate the Best Nash Equilibrium? SIAM J. Comput. 40(1): 79-91 (2011) - [j19]Robert Krauthgamer, Aranyak Mehta, Atri Rudra:
Pricing commodities. Theor. Comput. Sci. 412(7): 602-613 (2011) - [j18]Robert Krauthgamer, Tim Roughgarden:
Metric Clustering via Consistent Labeling. Theory Comput. 7(1): 49-74 (2011) - [c47]Nikhil Bansal, Uriel Feige, Robert Krauthgamer
Min-max Graph Partitioning and Small Set Expansion. FOCS 2011: 17-26 - [c46]Alexandr Andoni, Robert Krauthgamer
Streaming Algorithms via Precision Sampling. FOCS 2011: 363-372 - [c45]Michael Dinitz
Fault-tolerant spanners: better and simpler. PODC 2011: 169-178 - [c44]Lee-Ad Gottlieb, Robert Krauthgamer:
A Nonlinear Approach to Dimension Reduction. SODA 2011: 888-899 - [c43]Michael Dinitz
Directed spanners via flow-based linear programs. STOC 2011: 323-332 - [i13]Michael Dinitz, Robert Krauthgamer:
Fault-Tolerant Spanners: Better and Simpler. CoRR abs/1101.5753 (2011) - [i12]Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz:
Min-Max Graph Partitioning and Small Set Expansion. CoRR abs/1110.4319 (2011) - [i11]Lee-Ad Gottlieb, Aryeh Kontorovich, Robert Krauthgamer:
Efficient Regression in Metric Spaces via Approximate Lipschitz Extension. CoRR abs/1111.4470 (2011) - [i10]Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer:
The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme. CoRR abs/1112.0699 (2011) - 2010
- [j17]Alexandr Andoni, Robert Krauthgamer
The Computational Hardness of Estimating Edit Distance. SIAM J. Comput. 39(6): 2398-2429 (2010) - [c42]Eden Chlamtac, Robert Krauthgamer
Approximating Sparsest Cut in Graphs of Bounded Treewidth. APPROX-RANDOM 2010: 124-137 - [c41]Matthias Englert, Anupam Gupta, Robert Krauthgamer
Vertex Sparsifiers: New Results from Old Techniques. APPROX-RANDOM 2010: 152-165 - [c40]Lee-Ad Gottlieb
Proximity Algorithms for Nearly-Doubling Spaces. APPROX-RANDOM 2010: 192-204 - [c39]Lee-Ad Gottlieb, Leonid Kontorovich, Robert Krauthgamer:
Efficient Classification for Metric Data. COLT 2010: 433-440 - [c38]Alexandr Andoni, Robert Krauthgamer
Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. FOCS 2010: 377-386 - [p1]Alexandr Andoni, Robert Krauthgamer
Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. Property Testing 2010: 244-252 - [i9]Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak:
Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. CoRR abs/1005.4033 (2010) - [i8]Eden Chlamtac, Robert Krauthgamer, Prasad Raghavendra:
Approximating Sparsest Cut in Graphs of Bounded Treewidth. CoRR abs/1006.3970 (2010) - [i7]Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Räcke, Inbal Talgam-Cohen, Kunal Talwar:
Vertex Sparsifiers: New Results from Old Techniques. CoRR abs/1006.4586 (2010) - [i6]Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak:
Streaming Algorithms from Precision Sampling. CoRR abs/1011.1263 (2010) - [i5]Michael Dinitz, Robert Krauthgamer:
Directed Spanners via Flow-Based Linear Programs. CoRR abs/1011.3701 (2010)
2000 – 2009
- 2009
- [j16]Robert Krauthgamer
Improved Lower Bounds for Embeddings intoL1$. SIAM J. Comput. 38(6): 2487-2498 (2009) - [c37]Alexandr Andoni, Piotr Indyk, Robert Krauthgamer, Huy L. Nguyen:
Approximate line nearest neighbor in high dimensions. SODA 2009: 293-301 - [c36]Elad Hazan, Robert Krauthgamer:
How hard is it to approximate the best Nash equilibrium? SODA 2009: 720-727 - [c35]Alexandr Andoni, Piotr Indyk, Robert Krauthgamer:
Overcoming the l1 non-embeddability barrier: algorithms for product metrics. SODA 2009: 865-874 - [c34]Robert Krauthgamer, Joseph Naor, Roy Schwartz:
Partitioning graphs into balanced components. SODA 2009: 942-949 - [i4]Lee-Ad Gottlieb, Robert Krauthgamer:
A Nonlinear Approach to Dimension Reduction. CoRR abs/0907.5477 (2009) - 2008
- [c33]Alexandr Andoni, Robert Krauthgamer
The Smoothed Complexity of Edit Distance. ICALP (1) 2008: 357-369 - [c32]Robert Krauthgamer, Aranyak Mehta, Vijayshankar Raman, Atri Rudra:
Greedy List Intersection. ICDE 2008: 1033-1042 - [c31]Alexandr Andoni, Piotr Indyk, Robert Krauthgamer:
Earth mover distance over high-dimensional spaces. SODA 2008: 343-352 - [c30]Robert Krauthgamer, Tim Roughgarden:
Metric clustering via consistent labeling. SODA 2008: 809-818 - [r1]Robert Krauthgamer:
Minimum Bisection. Encyclopedia of Algorithms 2008 - 2007
- [j15]Robert Krauthgamer, James R. Lee:
The intrinsic dimensionality of graphs. Comb. 27(5): 551-585 (2007) - [j14]Eran Halperin, Guy Kortsarz, Robert Krauthgamer
Integrality Ratio for Group Steiner Trees and Directed Steiner Trees. SIAM J. Comput. 36(5): 1494-1511 (2007) - [c29]Alexandr Andoni, Robert Krauthgamer:
The Computational Hardness of Estimating Edit Distance [Extended Abstract]. FOCS 2007: 724-734 - [c28]Parikshit Gopalan, T. S. Jayram, Robert Krauthgamer, Ravi Kumar:
Estimating the sortedness of a data stream. SODA 2007: 318-327 - [c27]Robert Krauthgamer:
On triangulation of simple networks. SPAA 2007: 8-15 - [c26]Robert Krauthgamer
Pricing Commodities, or How to Sell When Buyers Have Restricted Valuations. WAOA 2007: 1-14 - [i3]Alexandr Andoni, Piotr Indyk, Robert Krauthgamer:
Earth Mover Distance over High-Dimensional Spaces. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [j13]Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani
On the Hardness of Approximating Multicut and Sparsest-Cut. Comput. Complex. 15(2): 94-114 (2006) - [j12]Robert Krauthgamer, Uriel Feige:
A Polylogarithmic Approximation of the Minimum Bisection. SIAM Rev. 48(1): 99-130 (2006) - [j11]Moses Charikar, Robert Krauthgamer:
Embedding the Ulam metric into l1. Theory Comput. 2(11): 207-224 (2006) - [c25]Robert Krauthgamer
Algorithms on negatively curved spaces. FOCS 2006: 119-132 - [c24]Robert Krauthgamer, Yuval Rabani:
Improved lower bounds for embeddings into L1. SODA 2006: 1010-1017 - 2005
- [j10]Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Robert Krauthgamer, Joseph Naor:
Asymmetric k-center is log* n-hard to approximate. J. ACM 52(4): 538-551 (2005) - [j9]Robert Krauthgamer, James R. Lee:
The black-box complexity of nearest-neighbor search. Theor. Comput. Sci. 348(2-3): 262-276 (2005) - [c23]Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani
On the Hardness of Approximating Multicut and Sparsest-Cut. CCC 2005: 144-153 - 2004
- [j8]Robert Krauthgamer, Nathan Linial, Avner Magen:
Metric Embeddings--Beyond One-Dimensional Distortion. Discret. Comput. Geom. 31(3): 339-356 (2004) - [j7]Guy Kortsarz, Robert Krauthgamer
Hardness of Approximation for Vertex-Connectivity Network Design Problems. SIAM J. Comput. 33(3): 704-720 (2004) - [c22]Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer
The Sketching Complexity of Pattern Matching. APPROX-RANDOM 2004: 261-272 - [c21]Robert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor:
Measured Descent: A New Embedding Method for Finite Metrics. FOCS 2004: 434-443 - [c20]Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer, Ravi Kumar:
Approximating Edit Distance Efficiently. FOCS 2004: 550-559 - [c19]Robert Krauthgamer
The Black-Box Complexity of Nearest Neighbor Search. ICALP 2004: 858-869 - [c18]Robert Krauthgamer, James R. Lee:
Navigating nets: simple algorithms for proximity search. SODA 2004: 798-807 - [c17]Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, Éva Tardos:
Approximate classification via earthmover metrics. SODA 2004: 1079-1087 - [c16]Kirsten Hildrum, Robert Krauthgamer, John Kubiatowicz:
Object location in realistic networks. SPAA 2004: 25-35 - [i2]Robert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor:
Measured descent: A new embedding method for finite metrics. CoRR abs/cs/0412008 (2004) - 2003
- [j6]Uriel Feige, Robert Krauthgamer, Kobbi Nissim:
On Cutting a Few Vertices from a Graph. Discret. Appl. Math. 127(3): 643-649 (2003) - [j5]Uriel Feige, Robert Krauthgamer
The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set. SIAM J. Comput. 32(2): 345-370 (2003) - [c15]Anupam Gupta, Robert Krauthgamer
Bounded Geometries, Fractals, and Low-Distortion Embeddings. FOCS 2003: 534-543 - [c14]Eran Halperin, Jeremy Buhler, Richard M. Karp, Robert Krauthgamer, Ben Westover:
Detecting protein sequence conservation via metric embeddings. ISMB (Supplement of Bioinformatics) 2003: 122-129 - [c13]Robert Krauthgamer, Ori Sasson:
Property testing of data dimensionality. SODA 2003: 18-27 - [c12]Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang:
Integrality ratio for group Steiner trees and directed steiner trees. SODA 2003: 275-284 - [c11]Eyal Amir, Robert Krauthgamer
Constant factor approximation of vertex-cuts in planar graphs. STOC 2003: 90-99 - [c10]Robert Krauthgamer
The intrinsic dimensionality of graphs. STOC 2003: 438-447 - [c9]Eran Halperin, Robert Krauthgamer
Polylogarithmic inapproximability. STOC 2003: 585-594 - [i1]Eran Halperin, Guy Kortsarz, Robert Krauthgamer:
Tight lower bounds for the asymmetric k-center problem. Electron. Colloquium Comput. Complex. TR03 (2003) - 2002
- [j4]Uriel Feige, Robert Krauthgamer
A Polylogarithmic Approximation of the Minimum Bisection. SIAM J. Comput. 31(4): 1090-1118 (2002) - [c8]Guy Kortsarz, Robert Krauthgamer
Hardness of Approximation for Vertex-Connectivity Network-Design Problems. APPROX 2002: 185-199 - 2001
- [j3]Guy Kortsarz, Robert Krauthgamer:
On Approximating the Achromatic Number. SIAM J. Discret. Math. 14(3): 408-422 (2001) - [c7]Guy Kortsarz, Robert Krauthgamer:
On approximating the achromatic number. SODA 2001: 309-318 - [c6]T. S. Jayram, Tracy Kimbrel, Robert Krauthgamer
Online server allocation in a server farm via benefit task systems. STOC 2001: 540-549 - [c5]Shai Halevi, Robert Krauthgamer
Private approximation of NP-hard functions. STOC 2001: 550-559 - 2000
- [j2]Uriel Feige, Robert Krauthgamer:
Networks on Which Hot-Potato Routing Does Not Livelock. Distributed Comput. 13(1): 53-58 (2000) - [j1]Uriel Feige, Robert Krauthgamer:
Finding and certifying a large hidden clique in a semirandom graph. Random Struct. Algorithms 16(2): 195-208 (2000) - [c4]Uriel Feige, Robert Krauthgamer:
A polylogarithmic approximation of the minimum bisection. FOCS 2000: 105-115 - [c3]Andrei Z. Broder, Robert Krauthgamer, Michael Mitzenmacher:
Improved classification via connectivity information. SODA 2000: 576-585 - [c2]Uriel Feige, Robert Krauthgamer
Approximating the minimum bisection size (extended abstract). STOC 2000: 530-536
1990 – 1999
- 1997
- [c1]Uriel Feige, Robert Krauthgamer:
Stereoscopic families of permutations, and their applications. ISTCS 1997: 85-95
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-12-26 01:54 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: