
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
- 2021
- [i61]Chen Amiraz, Robert Krauthgamer, Boaz Nadler:
Sparse Normal Means Estimation with Sublinear Communication. CoRR abs/2102.03060 (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, Ohad Trabelsi:
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 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, Barna Saha:
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
, Giuseppe F. Italiano, Robert Krauthgamer, Nikos Parotsidis
, Ohad Trabelsi, Przemyslaw Uznanski
, Daniel Wolleb-Graf:
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@SODA 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, Ilya P. Razenshteyn:
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
, Robert Krauthgamer:
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
, Aryeh Kontorovich
, Robert Krauthgamer:
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, Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Lin F. Yang:
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
, Robert Krauthgamer:
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
, Aryeh Kontorovich, Robert Krauthgamer:
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
, David P. Woodruff, Qin Zhang:
On Sketching Quadratic Forms. ITCS 2016: 311-319 - [c65]Rajesh Chitnis
, Lior Kamma, Robert Krauthgamer:
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
, Robert Krauthgamer:
A Nonlinear Approach to Dimension Reduction. Discret. Comput. Geom. 54(2): 291-315 (2015) - [j27]Lior Kamma, Robert Krauthgamer, Huy L. Nguyen:
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, Robert Krauthgamer, Tal Wagner:
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, Ilya P. Razenshteyn:
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. 22: 128 (2015) - 2014
- [j26]Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz:
Min-Max Graph Partitioning and Small Set Expansion. SIAM J. Comput. 43(2): 872-904 (2014) - [j25]Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Räcke, Inbal Talgam-Cohen, Kunal Talwar:
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
, Aryeh Kontorovich, Robert Krauthgamer:
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, Ely Porat, Shay Solomon:
Orienting Fully Dynamic Graphs with Worst-Case Time Bounds. ICALP (2) 2014: 532-543 - [c58]Amihood Amir, Jessica Ficler, Robert Krauthgamer, Liam Roditty, Oren Sar Shalom:
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
, Robert Krauthgamer:
Proximity Algorithms for Nearly Doubling Spaces. SIAM J. Discret. Math. 27(4): 1759-1769 (2013) - [c54]Lee-Ad Gottlieb
, Aryeh Kontorovich, Robert Krauthgamer:
Adaptive Metric Dimensionality Reduction. ALT 2013: 279-293 - [c53]Lee-Ad Gottlieb
, Aryeh Kontorovich, Robert Krauthgamer:
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, Robert Krauthgamer:
Everywhere-Sparse Spanners via Dense Subgraphs. FOCS 2012: 758-767 - [c49]Robert Krauthgamer, Tamar Zondiner:
Preserving Terminal Distances Using Minors. ICALP (1) 2012: 594-605 - [c48]Yair Bartal, Lee-Ad Gottlieb
, Robert Krauthgamer:
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
, Robert Krauthgamer:
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, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz:
Min-max Graph Partitioning and Small Set Expansion. FOCS 2011: 17-26 - [c46]Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak:
Streaming Algorithms via Precision Sampling. FOCS 2011: 363-372 - [c45]Michael Dinitz, Robert Krauthgamer:
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, Robert Krauthgamer:
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, Prasad Raghavendra:
Approximating Sparsest Cut in Graphs of Bounded Treewidth. APPROX-RANDOM 2010: 124-137 - [c41]Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Räcke, Inbal Talgam-Cohen, Kunal Talwar:
Vertex Sparsifiers: New Results from Old Techniques. APPROX-RANDOM 2010: 152-165 - [c40]Lee-Ad Gottlieb
, Robert Krauthgamer:
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, Krzysztof Onak:
Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. FOCS 2010: 377-386 - [p1]Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak:
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, Yuval Rabani:
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]