Bibtex entries for Robert Krauthgamer

@InProceedings{JKS24,
author = {Jiang, Shaofeng H.-C. and Krauthgamer, Robert and Sapir, Shay},
title = {{Moderate Dimension Reduction for $k$-Center Clustering}},
booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)},
pages = {64:1--64:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
year = {2024},
volume = {293},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
doi = {10.4230/LIPIcs.SoCG.2024.64},
}

@InProceedings{CGJKV24,
author = {Czumaj, Artur and Gao, Guichen and Jiang, Shaofeng H.-C. and Krauthgamer, Robert and Vesel\'{y}, Pavel},
title = {{Fully-Scalable MPC Algorithms for Clustering in High Dimension}},
booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
pages = {50:1--50:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
year = {2024},
volume = {297},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
doi = {10.4230/LIPIcs.ICALP.2024.50},
}

@InProceedings{KK24,
author = {Kenneth, Yotam and Krauthgamer, Robert},
title = {{Cut Sparsification and Succinct Representation of Submodular Hypergraphs}},
booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
pages = {97:1--97:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
year = {2024},
volume = {297},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
doi = {10.4230/LIPIcs.ICALP.2024.97},
}

@InProceedings{BKKS23,
author = {Braverman, Vladimir and Krauthgamer, Robert and Krishnan, Aditya and Sapir, Shay},
title = {Lower Bounds for Pseudo-Deterministic Counting in a Stream},
booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
pages = {30:1--30:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
year = {2023},
volume = {261},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
doi = {10.4230/LIPIcs.ICALP.2023.30},
}

@inproceedings{CJK23,
author = {Chen, Xiaoyu and Jiang, Shaofeng H.-C. and Krauthgamer, Robert},
title = {Streaming {Euclidean} Max-Cut: {Dimension} vs Data Reduction},
year = {2023},
isbn = {9781450399135},
publisher = {ACM},
booktitle = {Proceedings of the 55th Annual ACM Symposium on Theory of Computing},
pages = {170–182},
numpages = {13},
series = {STOC 2023},
doi = {10.1145/3564246.3585170},
}

@InProceedings{CDK23,
author = {Chakraborty, Diptarka and Das, Debarati and Krauthgamer, Robert},
title = {{Clustering Permutations: New Techniques with Streaming Applications}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {31:1--31:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
year = {2023},
volume = {251},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
doi = {10.4230/LIPIcs.ITCS.2023.31},
}

@InProceedings{GKKS23,
author = {Goldenberg, Elazar and Kociumaka, Tomasz and Krauthgamer, Robert and Saha, Barna},
title = {{An Algorithmic Bridge Between Hamming and Levenshtein Distances}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {58:1--58:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
year = {2023},
volume = {251},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
doi = {10.4230/LIPIcs.ITCS.2023.58},
}

@InProceedings{AKN24,
author = {Amiraz, Chen and Krauthgamer, Robert and Nadler, Boaz},
title = { Recovery Guarantees for Distributed-{OMP} },
booktitle = {27th International Conference on Artificial Intelligence and Statistics},
pages = {802--810},
year = {2024},
volume = {238},
series = {Proceedings of Machine Learning Research},
publisher = {PMLR},
ee = {https://proceedings.mlr.press/v238/amiraz24a.html},
}

@inproceedings{KM23,
author = {Robert Krauthgamer and Ron Mosenzon},
title = {Exact Flow Sparsification Requires Unbounded Size},
booktitle = {ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)},
pages = {2354-2367},
doi = {10.1137/1.9781611977554.ch91},
}

@inproceedings{BCJKSTW22,
author={Braverman, Vladimir and Cohen-Addad, Vincent and Jiang, H.-C. Shaofeng and Krauthgamer, Robert and Schwiegelshohn, Chris and Toftrup, Mads Bech and Wu, Xuan},
booktitle={63rd Annual Symposium on Foundations of Computer Science (FOCS)},
title={The Power of Uniform Sampling for Coresets},
year={2022},
pages={462-473},
doi={10.1109/FOCS54457.2022.00051},
}

@inproceedings{CJKVY22,
author={Czumaj, Artur and Jiang, Shaofeng H.-C. and Krauthgamer, Robert and Veselý, Pavel and Yang, Mingwei},
booktitle={63rd Annual Symposium on Foundations of Computer Science (FOCS)},
title={Streaming Facility Location in High Dimension via Geometric Hashing},
year={2022},
pages={450-461},
doi={10.1109/FOCS54457.2022.00050},
}

@article{KS23,
title={Comparison of Matrix Norm Sparsification},
author = {Robert Krauthgamer and Shay Sapir},
journal = {Algorithmica},
volume = {85},
pages = {3957–-3972},
year = 2023,
doi = {https://doi.org/10.1007/s00453-023-01172-6},
}

@inproceedings{AKLPST22,
author={Abboud, Amir and Krauthgamer, Robert and Li, Jason and Panigrahi, Debmalya and Saranurak, Thatchaphol and Trabelsi, Ohad},
booktitle={63rd Annual Symposium on Foundations of Computer Science (FOCS)},
title={Breaking the Cubic Barrier for {All-Pairs Max-Flow}: {G}omory-{H}u Tree in Nearly Quadratic Time},
year={2022},
pages={884-895},
doi={10.1109/FOCS54457.2022.00088},
}

@inproceedings{GKKS22,
author={Goldenberg, Elazar and Kociumaka, Tomasz and Krauthgamer, Robert and Saha, Barna},
booktitle={63rd Annual Symposium on Foundations of Computer Science (FOCS)},
title={Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal},
year={2022},
pages={674-685},
doi={10.1109/FOCS54457.2022.00070},
}

@inproceedings{CKZ22,
author = {Chang, {Hsien-Chih} and Krauthgamer, Robert and Tan, Zihan},
title = {Almost-Linear ε-Emulators for Planar Graphs},
year = {2022},
publisher = {Association for Computing Machinery},
pages = {1311–1324},
numpages = {14},
series = {STOC 2022},
doi = {10.1145/3519935.3519998},
}

@inproceedings{AKT22,
author = {Amir Abboud and Robert Krauthgamer and Ohad Trabelsi},
title = {Friendly Cut Sparsifiers and Faster {G}omory-{H}u Trees},
booktitle = {ACM-SIAM Symposium on Discrete Algorithms (SODA 2022)},
pages = {3630-3649},
doi = {10.1137/1.9781611977073.143},
}

@inproceedings{BJKW21,
author = {Braverman, Vladimir and Jiang, Shaofeng and Krauthgamer, Robert and Wu, Xuan},
booktitle = {Advances in Neural Information Processing Systems},
pages = {17360--17372},
publisher = {Curran Associates, Inc.},
title = {Coresets for Clustering with Missing Values},
ee = {https://proceedings.neurips.cc/paper/2021/hash/90fd4f88f588ae64038134f1eeaa023f-Abstract.html},
volume = {34},
year = {2021},
}

@Inproceedings{AKT21c,
author={Abboud, Amir and Krauthgamer, Robert and Trabelsi, Ohad},
booktitle={62nd Annual Symposium on Foundations of Computer Science (FOCS)},
title={APMF < APSP? {Gomory-Hu} Tree for Unweighted Graphs in Almost-Quadratic Time},
year={2021},
pages={1135-1146},
doi={10.1109/FOCS52979.2021.00112},
}

@Inproceedings{KKTY21b,
author={Kapralov, Michael and Krauthgamer, Robert and Tardos, Jakab and Yoshida, Yuichi},
booktitle={62nd Annual Symposium on Foundations of Computer Science (FOCS)},
title={Spectral Hypergraph Sparsifiers of Nearly Linear Size},
year={2021},
pages={1159-1170},
doi={10.1109/FOCS52979.2021.00114},
}

@article{JKLY24,
title={Coresets for kernel clustering},
author={Jiang, Shaofeng H. -C. and Krauthgamer, Robert and Lou, Jianing and Zhang, Yubo},
journal={Machine Learning},
year={2024},
volume={113},
doi={10.1007/s10994-024-06540-z},
number={8},
publisher={Springer},
pages={5891–5906},
}

@InProceedings{CDK21,
author = {Chakraborty, Diptarka and Das, Debarati and Krauthgamer, Robert},
title = {{Approximate Trace Reconstruction via Median String (In Average-Case)}},
booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
pages = {11:1--11:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
year = {2021},
volume = {213},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik},
doi = {10.4230/LIPIcs.FSTTCS.2021.11},
}

@article{CJKV24,
author = {Czumaj, Artur and Jiang, Shaofeng H.-C. and Krauthgamer, Robert and Vesel\'{y}, Pavel},
title = {Streaming Algorithms for Geometric Steiner Forest},
year = {2024},
publisher = {Association for Computing Machinery},
volume = {20},
number = {4},
doi = {10.1145/3663666},
journal = {ACM Trans. Algorithms},
articleno = {28},
numpages = {38},
} @InProceedings{CJKV22,
author = {Czumaj, Artur and Jiang, Shaofeng H.-C. and Krauthgamer, Robert and Vesel\'{y}, Pavel},
title = {{Streaming Algorithms for Geometric Steiner Forest}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {47:1--47:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
year = {2022},
volume = {229},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
doi = {10.4230/LIPIcs.ICALP.2022.47},
}

@InProceedings{BKKS21,
title = {Near-Optimal Entrywise Sampling of Numerically Sparse Matrices},
author = {Braverman, Vladimir and Krauthgamer, Robert and Krishnan, Aditya R. and Sapir, Shay},
booktitle = {Proceedings of 34th Conference on Learning Theory},
pages = {759--773},
year = {2021},
volume = {134},
series = {Proceedings of Machine Learning Research},
publisher = {PMLR},
ee = {http://proceedings.mlr.press/v134/braverman21b.html},
}

@article{KS22,
author = {Robert Krauthgamer and Shay Sapir},
title = {Smoothness of {Schatten} norms and sliding-window matrix streams},
journal = {Information Processing Letters},
volume = {177},
pages = {106254},
year = {2022},
issn = {0020-0190},
doi = {https://doi.org/10.1016/j.ipl.2022.106254},
}

@article{AKN22,
author = {Amiraz, Chen and Krauthgamer, Robert and Nadler, Boaz},
title = {Distributed Sparse Normal Means Estimation with Sublinear Communication},
journal = {Information and Inference: A Journal of the IMA},
year = {2022},
volume = {11},
number = {3},
pages = {1109-1142},
doi = {10.1093/imaiai/iaab030},
}

@inproceedings{AKT21b,
author = {Abboud, Amir and Krauthgamer, Robert and Trabelsi, Ohad},
title = {Subcubic Algorithms for {G}omory–{H}u Tree in Unweighted Graphs},
year = {2021},
publisher = {ACM},
doi = {10.1145/3406325.3451073},
booktitle = {Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing},
pages = {1725–1737},
series = {STOC 2021},
}

@inproceedings{KKTY21,
author = {Kapralov, Michael and Krauthgamer, Robert and Tardos, Jakab and Yoshida, Yuichi},
title = {Towards Tight Bounds for Spectral Sparsification of Hypergraphs},
year = {2021},
publisher = {ACM},
doi = {10.1145/3406325.3451061},
booktitle = {Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing},
pages = {598–611},
series = {STOC 2021},
}

@inproceedings{CDK21,
author = {Diptarka Chakraborty and Debarati Das and Robert Krauthgamer},
title = {Approximating the Median under the {U}lam Metric},
booktitle = {ACM-SIAM Symposium on Discrete Algorithms (SODA 2021)},
year = {2021},
pages = {761-775},
publisher = {SIAM},
doi = {10.1137/1.9781611976465.48},
}

@inproceedings{AKT20,
author={Abboud, Amir and Krauthgamer, Robert and Trabelsi, Ohad},
booktitle={61st Annual Symposium on Foundations of Computer Science (FOCS)},
title={Cut-Equivalent Trees are Optimal for Min-Cut Queries},
year={2020},
pages={105-118},
doi={10.1109/FOCS46700.2020.00019},
}

@inproceedings{BJKW21,
author = {Vladimir Braverman and Shaofeng H.-C. Jiang and Robert Krauthgamer and Xuan Wu},
title = {Coresets for Clustering in Excluded-Minor Graphs and Beyond},
booktitle = {ACM-SIAM Symposium on Discrete Algorithms (SODA 2021)},
year = {2021},
pages = {2679-2696},
publisher = {SIAM},
doi = {10.1137/1.9781611976465.159},
}

@article{AKT21,
author = {Abboud, Amir and Krauthgamer, Robert and Trabelsi, Ohad},
title = {New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs},
year = {2021},
pages = {1--27},
doi = {10.4086/toc.2021.v017a005},
publisher = {Theory of Computing},
journal = {Theory of Computing},
volume = {17},
number = {5},
}

@inproceedings{AKT20,
author = {Amir Abboud and Robert Krauthgamer and Ohad Trabelsi},
title = {New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs},
booktitle = {31st Annual ACM-SIAM Symposium on Discrete Algorithms},
year = {2020},
pages = {48-61},
publisher = {SIAM},
doi = {10.1137/1.9781611975994.4},
}

@article{BKY22,
author = {Braverman, Vladimir and Krauthgamer, Robert and Yang, Lin F.},
title = {Universal Streaming of Subset Norms},
year = {2022},
pages = {1--32},
doi = {10.4086/toc.2022.v018a020},
publisher = {Theory of Computing},
journal = {Theory of Computing},
volume = {18},
number = {20},
}

@article{FGK24,
author = {Arnold Filtser and Lee-Ad Gottlieb and Robert Krauthgamer},
title={Labelings vs. Embeddings: On Distributed and Prioritized Representations of Distances},
journal={Discrete \& Computational Geometry},
volume = {71},
pages = {849-–871},
publisher={Springer},
year = {2024},
doi = {https://doi.org/10.1007/s00454-023-00565-2},
}

@inproceedings{FGK20,
author = {Arnold Filtser and Lee-Ad Gottlieb and Robert Krauthgamer},
title = {Labelings vs. Embeddings: On Distributed Representations of Distances},
booktitle = {31st Annual ACM-SIAM Symposium on Discrete Algorithms},
year = {2020},
pages = {1063-1075},
publisher = {SIAM},
doi = {10.1137/1.9781611975994.65},
}

@inproceedings{BKKS20,
author = {Vladimir Braverman and Robert Krauthgamer and Aditya Krishnan and Roi Sinoff},
title = {Schatten Norms in Matrix Streams: {H}ello Sparsity, Goodbye Dimension},
booktitle = {Proceedings of the 37th International Conference on Machine Learning},
series = {Proceedings of Machine Learning Research},
volume = {119},
pages = {1100--1110},
publisher = {{PMLR}},
year = {2020},
}

@inproceedings{BBHJKW20,
author = {Daniel Baker and Vladimir Braverman and Lingxiao Huang and Shaofeng H.{-}C. Jiang and Robert Krauthgamer and Xuan Wu},
title = {Coresets for Clustering in Graphs of Bounded Treewidth},
booktitle = {37th International Conference on Machine Learning},
series = {Proceedings of Machine Learning Research},
volume = {119},
pages = {569--579},
publisher = {{PMLR}},
year = {2020},
url = {http://proceedings.mlr.press/v119/baker20a.html},
}

@article{GKR22,
author = {Lee-Ad Gottlieb and Robert Krauthgamer and Havana Rika},
title = {Faster algorithms for orienteering and $k$-TSP},
journal = {Theoretical Computer Science},
volume = {914},
pages = {73-83},
year = {2022},
issn = {0304-3975},
doi = {https://doi.org/10.1016/j.tcs.2022.02.013},
}

@Inproceedings{GKS19,
author={Elazar Goldenberg and Robert Krauthgamer and Barna Saha},
title={Sublinear Algorithms for Gap Edit Distance},
booktitle={60th Annual Symposium on Foundations of Computer Science},
year={2019},
pages={1101-1120},
doi={10.1109/FOCS.2019.00070},
publisher = {IEEE Computer Society},
}

@article{AKN20,
author = {Amiraz, Chen and Krauthgamer, Robert and Nadler, Boaz},
title = {Tight recovery guarantees for orthogonal matching pursuit under {G}aussian noise},
journal = {Information and Inference: A Journal of the IMA},
year = {2020},
volume = {10},
number = {2},
pages = {573–595},
doi = {10.1093/imaiai/iaaa021},
}

@article{KR22,
title = {Almost-Smooth Histograms and Sliding-Window Graph Algorithms},
author = {Krauthgamer, Robert and Reitblat, David},
journal = {Algorithmica},
volume = {84},
pages = {2926-–2953},
year = 2022,
doi = {10.1007/s00453-022-00988-y},
}

@InProceedings{BJKW19,
title = {Coresets for Ordered Weighted Clustering},
author = {Braverman, Vladimir and Jiang, Shaofeng H.-C. and Krauthgamer, Robert and Wu, Xuan},
booktitle = {36th International Conference on Machine Learning},
pages = {744--753},
year = {2019},
volume = {97},
series = {Proceedings of Machine Learning Research},
publisher = {PMLR},
url = {http://proceedings.mlr.press/v97/braverman19a.html},
}

@InProceedings{AKP19,
author = {Alexandr Andoni and Robert Krauthgamer and Yosef Pogrow},
title = {{On Solving Linear Systems in Sublinear Time}},
booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
pages = {3:1--3:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
year = {2018},
volume = {124},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
doi = {10.4230/LIPIcs.ITCS.2019.3},
}

@InProceedings{FKT19,
author = {Arnold Filtser and Robert Krauthgamer and Ohad Trabelsi},
title = {{Relaxed Voronoi: A Simple Framework for Terminal-Clustering Problems}},
booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)},
pages = {10:1--10:14},
series = {OpenAccess Series in Informatics (OASIcs)},
year = {2019},
volume = {69},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
doi = {10.4230/OASIcs.SOSA.2019.10},
}

@inproceedings{KLR19,
author = {Robert Krauthgamer and James R. Lee and Havana (Inbal) Rika},
title = {Flow-Cut Gaps and Face Covers in Planar Graphs},
booktitle = {30th Annual ACM-SIAM Symposium on Discrete Algorithms},
year = {2019},
pages = {525-534},
doi = {10.1137/1.9781611975482.33},
}

@InProceedings{AGIKPTUW19,
author = {Amir Abboud and Loukas Georgiadis and Giuseppe F. Italiano and Robert Krauthgamer and Nikos Parotsidis and Ohad Trabelsi and Przemyslaw Uznanski and Daniel Wolleb-Graf},
title = {{Faster Algorithms for All-Pairs Bounded Min-Cuts}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {7:1--7:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
year = {2019},
volume = {132},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
doi = {10.4230/LIPIcs.ICALP.2019.7},
}

@InProceedings{KT19,
author = {Robert Krauthgamer and Ohad Trabelsi},
title = {{The Set Cover Conjecture and Subgraph Isomorphism with a Tree Pattern}},
booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
pages = {45:1--45:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
year = {2019},
volume = {126},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
doi = {10.4230/LIPIcs.STACS.2019.45},
}


@article{KR20,
author = {Krauthgamer, Robert and Rika, Havana (Inbal)},
title = {Refined Vertex Sparsifiers of Planar Graphs},
journal = {SIAM Journal on Discrete Mathematics},
volume = {34},
number = {1},
pages = {101-129},
year = {2020},
doi = {10.1137/17M1151225},
}

@article{KT18,
author = {Krauthgamer, Robert and Trabelsi, Ohad},
title = {Conditional Lower Bounds for All-Pairs Max-Flow},
journal = {ACM Trans. Algorithms},
volume = {14},
number = {4},
pages = {42:1--42:15},
articleno = {42},
numpages = {15},
doi = {10.1145/3212510},
publisher = {ACM},
}

@InProceedings{KT17,
author = {Robert Krauthgamer and Ohad Trabelsi},
title = {Conditional Lower Bounds for {A}ll-{P}airs {M}ax-{F}low}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming},
pages = {20:1--20:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
year = {2017},
volume = {80},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
doi = {10.4230/LIPIcs.ICALP.2017.20},
}

@InProceedings{CKK16,
author={Chitnis, Rajesh and Kamma, Lior and Krauthgamer, Robert},
title={Tight Bounds for {G}omory-{H}u-like Cut Counting},
bookTitle={42nd International Workshop on Graph-Theoretic Concepts in Computer Science},
series={WG 2016},
year=2016,
publisher={Springer},
pages={133--144},
doi={10.1007/978-3-662-53536-3_12},
}

@article{FK17,
author = {Arnold Filtser and Robert Krauthgamer},
title = {Sparsification of Two-Variable Valued Constraint Satisfaction Problems},
journal = {SIAM Journal on Discrete Mathematics},
volume = {31},
number = {2},
pages = {1263-1276},
year = {2017},
doi = {10.1137/15M1046186},
}

@InProceedings{BCKLWY18,
title = {Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order},
author = {Braverman, Vladimir and Chestnut, Stephen and Krauthgamer, Robert and Li, Yi and Woodruff, David and Yang, Lin F.},
booktitle = {35th International Conference on Machine Learning},
pages = {649--658},
year = {2018},
volume = {80},
series = {Proceedings of Machine Learning Research},
publisher = {PMLR},
url = {http://proceedings.mlr.press/v80/braverman18a.html},
}

@InProceedings{KK16,
author = {Tsvi Kopelowitz and Robert Krauthgamer},
title = {Color-Distance Oracles and Snippets},
booktitle = {27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)},
pages = {24:1--24:10},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
year = {2016},
volume = {54},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
doi = {10.4230/LIPIcs.CPM.2016.24},
}

@inproceedings{BBCKY17,
author = {B\l{}asiok, Jaros\l{}aw and Braverman, Vladimir and Chestnut, Stephen R. and Krauthgamer, Robert and Yang, Lin F.},
title = {Streaming Symmetric Norms via Measure Concentration},
booktitle = {49th Annual ACM Symposium on Theory of Computing},
series = {STOC 2017},
year = {2017},
pages = {716--729},
doi = {10.1145/3055399.3055424},
publisher = {ACM},
}

@article{DGK17,
author = {David, Roee and Goldenberg, Elazar and Krauthgamer, Robert},
title = {Local reconstruction of low-rank matrices and subspaces},
journal = {Random Structures \& Algorithms},
volume = {51},
number = {4},
issn = {1098-2418},
doi = {10.1002/rsa.20720},
pages = {607--630},
year = {2017},
}

@InProceedings{DKW15,
author = {Michael Dinitz and Robert Krauthgamer and Tal Wagner},
title = {Towards Resistance Sparsifiers},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
pages = {738--755},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
year = {2015},
volume = {40},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.738},
}

@InProceedings{ACKW15,
author = {Ittai Abraham and Shiri Chechik and Robert Krauthgamer and Udi Wieder},
title = {Approximate Nearest Neighbor Search in Metrics of Planar Graphs},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
pages = {20--42},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
year = {2015},
volume = {40},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.20},
}

@article{KK17,
author="Kamma, Lior and Krauthgamer, Robert",
title="Metric Decompositions of Path-Separable Graphs",
journal="Algorithmica",
year="2017",
volume="79",
number="3",
pages="645--653",
doi="10.1007/s00453-016-0213-0",
}

@inproceedings{AKR15,
author = {Andoni, Alexandr and Krauthgamer, Robert and Razenshteyn, Ilya},
title = {Sketching and Embedding Are Equivalent for Norms},
booktitle = {47th Annual ACM Symposium on Theory of Computing},
year = {2015},
isbn = {978-1-4503-3536-2},
pages = {479--488},
numpages = {10},
doi = {10.1145/2746539.2746552},
publisher = {ACM},
}

@inproceedings{KK15,
author = {Kogan, Dmitry and Krauthgamer, Robert},
title = {Sketching Cuts in Graphs and Hypergraphs},
booktitle = {Conference on Innovations in Theoretical Computer Science},
year = {2015},
isbn = {978-1-4503-3333-7},
pages = {367--376},
numpages = {10},
doi = {10.1145/2688073.2688093},
publisher = {ACM},
}

@article{KW16,
author = {Krauthgamer, Robert and Wagner, Tal},
title = {Cheeger-Type Approximation for Sparsest st-Cut},
journal = {ACM Trans. Algorithms},
volume = {13},
number = {1},
year = {2016},
issn = {1549-6325},
pages = {14:1--14:21},
numpages = {21},
doi = {10.1145/2996799},
publisher = {ACM},
}

@inproceedings{AAKK14,
author = {Abdullah, Amirali and Andoni, Alexandr and Kannan, Ravindran and Krauthgamer, Robert},
title = {Spectral Approaches to Nearest Neighbor Search},
booktitle = {55th Annual Symposium on Foundations of Computer Science},
year = {2014},
isbn = {978-1-4799-6517-5},
pages = {581--590},
numpages = {10},
doi = {10.1109/FOCS.2014.68},
publisher = {IEEE Computer Society},
}

@inproceedings{ACKQWZ16,
author = {Andoni, Alexandr and Chen, Jiecao and Krauthgamer, Robert and Qin, Bo and Woodruff, David P. and Zhang, Qin},
title = {On Sketching Quadratic Forms},
booktitle = {Innovations in Theoretical Computer Science},
series = {ITCS'16},
year = {2016},
isbn = {978-1-4503-4057-1},
pages = {311--319},
numpages = {9},
doi = {10.1145/2840728.2840753},
publisher = {ACM},
}

@incollection{KKPS14,
author={Kopelowitz, Tsvi and Krauthgamer, Robert and Porat, Ely and Solomon, Shay},
title={Orienting Fully Dynamic Graphs with Worst-Case Time Bounds},
year={2014},
isbn={978-3-662-43950-0},
booktitle={Automata, Languages, and Programming},
volume={8573},
series={Lecture Notes in Computer Science},
pages={532-543},
doi={10.1007/978-3-662-43951-7_45},
publisher={Springer},
}

@incollection{AFKRS14,
title={Multiply Balanced $k$-Partitioning},
author={Amir, Amihood and Ficler, Jessica and Krauthgamer, Robert and Roditty, Liam and Sar Shalom, Oren},
year={2014},
isbn={978-3-642-54422-4},
booktitle={LATIN 2014: Theoretical Informatics},
volume={8392},
series={Lecture Notes in Computer Science},
doi={10.1007/978-3-642-54423-1_51},
publisher={Springer},
pages={586-597}
}


@inproceedings{AGK14,
author = {Andoni, A. and Gupta, A. and Krauthgamer, R.},
title = {Towards $(1+\epsilon)$-Approximate Flow Sparsifiers},
booktitle = {25th Annual ACM-SIAM Symposium on Discrete Algorithms},
year={2014},
pages = {279-293},
publisher = {SIAM},
doi = {10.1137/1.9781611973402.20},
}


@inproceedings{KNST14,
author = {Krauthgamer, R. and Naor, J. and Schwartz, R. and Talwar, K.},
title = {Non-Uniform Graph Partitioning},
booktitle = {25th Annual ACM-SIAM Symposium on Discrete Algorithms},
year={2014},
pages = {1229-1243},
publisher = {SIAM},
doi = {10.1137/1.9781611973402.91},
}

@article{KNV15,
AUTHOR = {Krauthgamer, Robert and Nadler, Boaz and Vilenchik, Dan},
TITLE = {Do semidefinite relaxations solve sparse {PCA} up to the information limit?},
JOURNAL = {Ann. Statist.},
FJOURNAL = {The Annals of Statistics},
VOLUME = {43},
YEAR = {2015},
NUMBER = {3},
PAGES = {1300--1322},
ISSN = {0090-5364},
DOI = {10.1214/15-AOS1310},
}

@article{KKN15,
author = {Lior Kamma and Robert Krauthgamer and Huy L. Nguyen},
title = {Cutting Corners Cheaply, or How to Remove Steiner Points},
journal = {SIAM Journal on Computing},
volume = {44},
number = {4},
pages = {975-995},
year = {2015},
doi = {10.1137/140951382},
}

@inproceedings{KKN14,
author = {Kamma, L. and Krauthgamer, R. and Nguyen, H.},
title = {Cutting corners cheaply, or how to remove Steiner points},
booktitle = {25th Annual ACM-SIAM Symposium on Discrete Algorithms},
year={2014},
pages = {1029-1040},
publisher = {SIAM},
doi = {10.1137/1.9781611973402.77},
}

@article{GKK16,
author = {Lee-Ad Gottlieb and Aryeh Kontorovich and Robert Krauthgamer},
title = {Adaptive metric dimensionality reduction},
journal = {Theor. Comput. Sci.},
volume = {620},
pages = {105--118},
year = {2016},
doi = {10.1016/j.tcs.2015.10.040},
}

@incollection{GKK13b,
title={Adaptive Metric Dimensionality Reduction},
author={Gottlieb, Lee-Ad and Kontorovich, Aryeh and Krauthgamer, Robert},
pages={279-293},
year={2013},
isbn={978-3-642-40934-9},
booktitle={Algorithmic Learning Theory},
volume={8139},
series={Lecture Notes in Computer Science},
doi={10.1007/978-3-642-40935-6_20},
publisher={Springer},
}

@inproceedings{KR13,
author = {Robert Krauthgamer and Inbal Rika},
title = {Mimicking Networks and Succinct Representations of Terminal Cuts},
year = {2013},
pages = {1789-1799},
doi = {10.1137/1.9781611973105.128},
booktitle = {24th Annual ACM-SIAM Symposium on Discrete Algorithms},
publisher = {SIAM},
}

@inproceedings{CDK12,
author = {Chlamtac, Eden and Dinitz, Michael and Krauthgamer, Robert},
title = {Everywhere-Sparse Spanners via Dense Subgraphs},
booktitle = {IEEE 53rd Annual Symposium on Foundations of Computer Science},
year = {2012},
isbn = {978-0-7695-4874-6},
pages = {758--767},
doi = {10.1109/FOCS.2012.61},
publisher = {IEEE Computer Society},
}


@article{KNZ14,
author = {Krauthgamer, R. and Nguyen, H. and Zondiner, T.},
title = {Preserving Terminal Distances Using Minors},
journal = {SIAM Journal on Discrete Mathematics},
volume = {28},
number = {1},
pages = {127-141},
year = {2014},
doi = {10.1137/120888843},
}

@inproceedings{KZ12,
author = {Robert Krauthgamer and Tamar Zondiner},
title = {Preserving Terminal Distances Using Minors},
year = {2012},
pages = {594-605},
doi = {10.1007/978-3-642-31594-7_50},
booktitle = {39th International Colloquium on Automata, Languages, and Programming},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = {7391},
}


@article{BGK16,
author = {Yair Bartal and Lee-Ad Gottlieb and Robert Krauthgamer},
title = {The {T}raveling {S}alesman {P}roblem: {L}ow-Dimensionality Implies a Polynomial Time Approximation Scheme},
journal = {SIAM Journal on Computing},
volume = {45},
number = {4},
pages = {1563-1581},
year = {2016},
doi = {10.1137/130913328},
}

@inproceedings{BGK12,
author = {Bartal, Yair and Gottlieb, Lee-Ad and Krauthgamer, Robert},
title = {The traveling salesman problem: {L}ow-dimensionality implies a polynomial time approximation scheme},
booktitle = {44th Symposium on Theory of Computing},
year = {2012},
isbn = {978-1-4503-1245-5},
pages = {663--672},
numpages = {10},
doi = {10.1145/2213977.2214038},
publisher = {ACM},
}

@article{GKK17,
author={Gottlieb, Lee-Ad and Kontorovich, Aryeh and Krauthgamer, Robert},
journal={IEEE Transactions on Information Theory},
title={Efficient Regression in Metric Spaces via Approximate {L}ipschitz Extension},
year={2017},
volume={63},
number={8},
pages={4838-4849},
doi={10.1109/TIT.2017.2713820},
}

@incollection{GKK13a,
title={Efficient Regression in Metric Spaces via Approximate {L}ipschitz Extension},
author={Gottlieb, Lee-Ad and Kontorovich, Aryeh and Krauthgamer, Robert},
pages={43-58},
year={2013},
isbn={978-3-642-39139-2},
booktitle={Similarity-Based Pattern Recognition},
volume={7953},
series={Lecture Notes in Computer Science},
doi={10.1007/978-3-642-39140-8_3},
publisher={Springer},
}

@article{BFKMNNS14,
author = {Nikhil Bansal and Uriel Feige and Robert Krauthgamer and Konstantin Makarychev and Viswanath Nagarajan and Joseph (Seffi) Naor and Roy Schwartz},
title = {Min-Max Graph Partitioning and Small Set Expansion},
journal = {SIAM Journal on Computing},
volume = {43},
number = {2},
pages = {872-904},
year = {2014},
doi = {10.1137/120873996},
}

@inproceedings{BFKMNNS11,
author = {Bansal, Nikhil and Feige, Uriel and Krauthgamer, Robert and Makarychev, Konstantin and Nagarajan, Viswanath and Naor, Joseph (Seffi) and Schwartz, Roy},
title = {Min-max Graph Partitioning and Small Set Expansion},
booktitle = {IEEE 52nd Annual Symposium on Foundations of Computer Science},
year = {2011},
isbn = {978-0-7695-4571-4},
pages = {17--26},
numpages = {10},
doi = {10.1109/FOCS.2011.79},
publisher = {IEEE Computer Society},
}

@inproceedings{AKO11,
author = {Andoni, Alexandr and Krauthgamer, Robert and Onak, Krzysztof},
title = {Streaming Algorithms via Precision Sampling},
booktitle = {IEEE 52nd Annual Symposium on Foundations of Computer Science},
year = {2011},
isbn = {978-0-7695-4571-4},
pages = {363--372},
numpages = {10},
doi = {10.1109/FOCS.2011.82},
publisher = {IEEE Computer Society},
}

@inproceedings{DK11b,
author = {Dinitz, Michael and Krauthgamer, Robert},
title = {Fault-tolerant spanners: better and simpler},
booktitle = {30th Annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing},
year = {2011},
pages = {169--178},
doi = {10.1145/1993806.1993830},
publisher = {ACM},
}

@inproceedings{DK11a,
author = {Dinitz, Michael and Krauthgamer, Robert},
title = {Directed spanners via flow-based linear programs},
booktitle = {43rd Annual ACM Symposium on Theory of Computing},
year = {2011},
pages = {323--332},
doi = {10.1145/1993636.1993680},
publisher = {ACM},
}

@inproceedings{CKR10,
author = {Eden Chlamtac and Robert Krauthgamer and Prasad Raghavendra},
title = {Approximating Sparsest Cut in Graphs of Bounded Treewidth},
pages = {124-137},
doi = {10.1007/978-3-642-15369-3_10},
booktitle = {13th International Workshop on Approximation, Randomization, and Combinatorial Optimization},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = {6302},
year = {2010},
isbn = {978-3-642-15368-6},
}

@article{EGKRTT14,
author = {Englert, M. and Gupta, A. and Krauthgamer, R. and R{\"a}cke, H. and Talgam-Cohen, I. and Talwar, K.},
title = {Vertex Sparsifiers: New Results from Old Techniques},
journal = {SIAM Journal on Computing},
volume = {43},
number = {4},
pages = {1239-1262},
year = {2014},
doi = {10.1137/130908440},
eprint = {1006.4586},
}

@inproceedings{EGKRTT10,
author = {Matthias Englert and Anupam Gupta and Robert Krauthgamer and Harald R{\"a}cke and Inbal Talgam-Cohen and Kunal Talwar},
title = {Vertex Sparsifiers: New Results from Old Techniques},
pages = {152-165},
doi = {10.1007/978-3-642-15369-3_12},
booktitle = {13th International Workshop on Approximation, Randomization, and Combinatorial Optimization},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = {6302},
year = {2010},
isbn = {978-3-642-15368-6},
}

@article{GK13,
author = {Lee-Ad Gottlieb and Robert Krauthgamer},
title = {Proximity Algorithms for Nearly Doubling Spaces},
journal = {SIAM J. Discrete Math.},
volume = {27},
number = {4},
year = {2013},
pages = {1759-1769},
doi = {10.1137/120874242},
}

@inproceedings{GK10,
author = {Lee-Ad Gottlieb and Robert Krauthgamer},
title = {Proximity Algorithms for Nearly-Doubling Spaces},
booktitle = {13th International Workshop on Approximation, Randomization, and Combinatorial Optimization},
pages = {192-204},
doi = {10.1007/978-3-642-15369-3_15},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = {6302},
year = {2010},
}

@article{GKK14,
author={Gottlieb, L. and Kontorovich, A. and Krauthgamer, R.},
journal={Information Theory, IEEE Transactions on},
title={Efficient Classification for Metric Data},
year={2014},
month={Sept},
volume={60},
number={9},
pages={5750-5759},
doi={10.1109/TIT.2014.2339840},
issn={0018-9448},
}

@inproceedings{GKK10,
author = {Lee-Ad Gottlieb and Aryeh Kontorovich and Robert Krauthgamer},
title = {Efficient Classification for Metric Data},
pages = {433-440},
url = {http://www.learningtheory.org/colt2010/papers/031Gottlieb.pdf},
booktitle = {23rd Conference on Learning Theory},
publisher = {Omnipress},
year = {2010},
isbn = {978-0-9822529-2-5},
}

@inproceedings{AKO10,
author={Andoni, A. and Krauthgamer, R. and Onak, K.},
booktitle={51st Annual IEEE Symposium on Foundations of Computer Science},
title={Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity},
year={2010},
pages={377 -386},
doi={10.1109/FOCS.2010.43},
}

@article{HK11,
author = {Hazan, Elad and Krauthgamer, Robert},
title = {How Hard Is It to Approximate the Best Nash Equilibrium?},
journal = {SIAM J. Comput.},
volume = {40},
number = {1},
month = jan,
year = {2011},
issn = {0097-5397},
pages = {79--91},
numpages = {13},
doi = {10.1137/090766991},
publisher = {SIAM},
}

@inproceedings{HK09,
author = {Hazan, E. and Krauthgamer, R.},
title = {How hard is it to approximate the best Nash equilibrium?},
booktitle = {19th Annual ACM-SIAM Symposium on Discrete Algorithms},
year = {2009},
pages = {720--727},
publisher = {SIAM},
doi = {10.1137/1.9781611973068.79},
}

@article{GK15,
title={A Nonlinear Approach to Dimension Reduction},
author={Gottlieb, Lee-Ad and Krauthgamer, Robert},
year={2015},
volume={54},
number={2},
issn={0179-5376},
journal={Discrete \& Computational Geometry},
publisher={Springer},
pages={291--315},
doi={10.1007/s00454-015-9707-9},
}

@inproceedings{GK11,
author = {Lee-Ad Gottlieb and Robert Krauthgamer},
title = {A Nonlinear Approach to Dimension Reduction},
booktitle = {21st Annual ACM-SIAM Symposium on Discrete Algorithms},
year = {2011},
pages = {888--899},
publisher = {SIAM},
doi={10.1137/1.9781611973082.69},
}

@inproceedings{KNS09,
author = {Krauthgamer, R. and Naor, J. and Schwartz, R.},
title = {Partitioning graphs into balanced components},
booktitle = {19th Annual ACM-SIAM Symposium on Discrete Algorithms},
year = {2009},
pages = {942--949},
publisher = {SIAM},
doi = {10.1137/1.9781611973068.102},
}

@inproceedings{AIKN09,
author = {Andoni, A. and Indyk, P. and Krauthgamer, R. and Nguyen, H. L.},
title = {Approximate line nearest neighbor in high dimensions},
booktitle = {19th Annual ACM-SIAM Symposium on Discrete Algorithms},
year = {2009},
pages = {293--301},
publisher = {SIAM},
doi = {10.1137/1.9781611973068.33},
}

@inproceedings{AIK09,
author = {Andoni, A. and Indyk, P. and Krauthgamer, R.},
title = {Overcoming the $l_1$ non-embeddability barrier: algorithms for product metrics},
booktitle = {19th Annual ACM-SIAM Symposium on Discrete Algorithms},
year = {2009},
pages = {865--874},
publisher = {SIAM},
doi = {10.1137/1.9781611973068.94},
}

@article{AK12,
title = {The smoothed complexity of edit distance},
author = {Andoni, Alexandr and Krauthgamer, Robert},
journal = {ACM Trans. Algorithms},
volume = {8},
number = {4},
month = oct,
year = {2012},
issn = {1549-6325},
pages = {44:1--44:25},
articleno = {44},
numpages = {25},
doi = {10.1145/2344422.2344434},
publisher = {ACM},
}

@inproceedings{AK08,
title={The Smoothed Complexity of Edit Distance},
author={A. Andoni and R. Krauthgamer},
booktitle = {35st International Colloquium on Automata, Languages and Programming},
pages = {357--369},
year = {2008},
series = {Lecture Notes in Computer Science},
vol={5125},
publisher={Springer},
}

@inproceedings{AIK08,
author = {A. Andoni and P. Indyk and R. Krauthgamer},
title = {Earth Mover Distance over High-Dimensional Spaces},
booktitle = {19th annual ACM-SIAM symposium on Discrete algorithms},
year = 2008,
pages={343--352},
url={http://dl.acm.org/citation.cfm?id=1347082.1347120},
}


@article{KR11,
author = {Robert Krauthgamer and Tim Roughgarden},
title = {Metric Clustering via Consistent Labeling},
year = {2011},
pages = {49-74},
doi = {10.4086/toc.2011.v007a005},
publisher = {Theory of Computing},
journal = {Theory of Computing},
volume = {7},
number = {5},
}

@inproceedings{KR08,
title={Metric Clustering via Consistent Labeling},
author={R. Krauthgamer and T. Roughgarden},
booktitle = {19th annual ACM-SIAM symposium on Discrete Algorithms},
year=2008,
pages={809--818},
url={http://dl.acm.org/citation.cfm?id=1347082.1347171},
}

@article{AK10,
author = {Andoni, Alexandr and Krauthgamer, Robert},
title = {The Computational Hardness of Estimating Edit Distance},
journal = {SIAM J. Comput.},
volume = {39},
number = {6},
year = {2010},
issn = {0097-5397},
pages = {2398--2429},
numpages = {32},
doi = {10.1137/080716530},
publisher = {SIAM},
}

@inproceedings{AK07,
title={The Computational Hardness of Estimating Edit Distance},
author={Alexandr Andoni and Robert Krauthgamer},
booktitle = {48th Annual IEEE Symposium on Foundations of Computer Science},
pages={724-734},
year=2007,
publisher={IEEE},
}

@inproceedings{KMRR07,
author = {R. Krauthgamer and A. Mehta and V. Raman and A. Rudra},
title = {Greedy List Intersection},
booktitle = {24th International Conference on Data Engineering (ICDE)},
year = {2008},
pages = {1033-1042},
doi = {10.1109/ICDE.2008.4497512},
}


@article{KMR11,
title = "Pricing commodities",
author = "Robert Krauthgamer and Aranyak Mehta and Atri Rudra",
journal = "Theoretical Computer Science",
volume = "412",
number = "7",
pages = "602 - 613",
year = "2011",
doi = "10.1016/j.tcs.2009.10.002",
} @inproceedings{KMR07,
author = {R. Krauthgamer and A. Mehta and A. Rudra},
title = {Pricing Commodities, or How to Sell When Buyers Have Restricted Valuations},
booktitle = {5th International Workshop on Approximation and Online Algorithms (WAOA)},
year = {2007},
pages = {1-14},
doi = {10.1007/978-3-540-77918-6_1},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = {4927},
}

@inproceedings{Kra07,
author = {Robert Krauthgamer},
title = {On triangulation of simple networks},
year = {2007},
pages = {8-15},
booktitle = {Proceedings of the 19th Annual ACM Symposium
on Parallel Algorithms and Architectures},
publisher = {ACM},
}

@inproceedings{GJKK07,
author = {P. Gopalan and T. S. Jayram and R. Krauthgamer and R. Kumar},
title = {Estimating the sortedness of a data stream},
pages = {318-327},
booktitle = {18th Annual ACM-SIAM Symposium on Discrete Algorithms},
publisher = {SIAM},
year = {2007},
url = {https://dl.acm.org/doi/10.5555/1283383.1283417},
}

@inproceedings{KL06,
author = {R. Krauthgamer and J. R. Lee},
title = {Algorithms on negatively curved spaces},
year = {2006},
pages = {119-132},
doi = {10.1109/FOCS.2006.9},
booktitle = {47th Annual IEEE Symposium on Foundations of Computer Science},
publisher = {IEEE Computer Society},
}

@article{CK06,
author = {Moses Charikar and Robert Krauthgamer},
title = {Embedding the {U}lam metric into $\ell_1$},
journal = {Theory of Computing},
year = {2006}, volume = {2},
number = {11},
pages = {207--224},
publisher = {Theory of Computing},
eprint = {toc:v002/a011},
doi = {10.4086/toc.2006.v002a011},
}

@article{KR09,
author = {R. Krauthgamer and Y. Rabani},
title = {Improved Lower Bounds for Embeddings intoL$_{\mbox{1}}$\$},
journal = {SIAM J. Comput.},
volume = {38},
number = {6},
year = {2009},
pages = {2487-2498},
doi = {10.1137/060660126},
}

@inproceedings{KR06,
author = {Robert Krauthgamer and Yuval Rabani},
title = {Improved lower bounds for embeddings into $L_1$},
booktitle = {Proceedings of the 17th annual ACM-SIAM symposium on Discrete algorithm},
year = {2006},
pages = {1010--1017},
publisher = {ACM Press},
url = {http://dl.acm.org/citation.cfm?id=1109557.1109669},
}

@article{CKKRS06,
author = {S. Chawla and R. Krauthgamer and R. Kumar and Y. Rabani and D. Sivakumar},
title = {On the Hardness of Approximating Multicut and Sparsest-Cut},
journal = {Computational Complexity},
volume = {15},
number = {2},
year = {2006},
pages = {94-114},
doi = {10.1007/s00037-006-0210-9},
}

@inproceedings{CKKRS05,
author={S. Chawla and R. Krauthgamer and R. Kumar and Y. Rabani and D. Sivakumar},
title={On the hardness of approximating multicut and sparsest-cut},
booktitle ={20th Annual IEEE Conference on Computational Complexity},
year={2005},
pages={144--153},
}

@incollection {BJKK04b,
AUTHOR={Z. Bar-Yossef and T. S. Jayram and Robert Krauthgamer and Ravi Kumar},
TITLE = {The sketching complexity of pattern matching},
BOOKTITLE = {8th International Workshop on Randomization and Computation},
PAGES = {261--272},
SERIES={Lecture Notes in Computer Science},
PUBLISHER = {Springer},
YEAR = {2004},
DOI={10.1007/978-3-540-27821-4_24},
}

@inproceedings{BJKK04,
title={Approximating edit distance efficiently},
author={Z. Bar-Yossef and T. S. Jayram and Robert Krauthgamer and Ravi Kumar},
booktitle = {45th Annual IEEE Symposium on Foundations of Computer Science},
pages={550-559},
year=2004,
publisher={IEEE},
doi = {10.1109/FOCS.2004.14},
}

@article{KLMN05,
title={Measured descent: {A} new embedding method for finite metrics},
author={R. Krauthgamer and J. R. Lee and M. Mendel and A. Naor},
journal={Geometric And Functional Analysis},
volume={15},
number={4},
year=2005,
pages={839--858},
doi={10.1007/s00039-005-0527-6},
}

@inproceedings{KLMN04,
title={Measured descent: {A} new embedding method for finite metrics},
author={R. Krauthgamer and J. R. Lee and M. Mendel and A. Naor},
booktitle = {45th Annual IEEE Symposium on Foundations of Computer Science},
pages={434--443},
year=2004,
publisher={IEEE},
}

@article {KL05,
AUTHOR = {Krauthgamer, R. and Lee, J. R.},
TITLE = {The black-box complexity of nearest-neighbor search},
JOURNAL = {Theoret. Comput. Sci.},
FJOURNAL = {Theoretical Computer Science},
VOLUME = {348},
YEAR = {2005},
NUMBER = {2-3},
PAGES = {262--276},
DOI={10.1016/j.tcs.2005.09.017},
}

@inproceedings{KL04b,
TITLE={The black-box complexity of nearest neighbor search},
AUTHOR={R. Krauthgamer and J. R. Lee},
BOOKTITLE = {31st International Colloquium on Automata, Languages and Programming},
PAGES = {858--869},
YEAR = {2004},
SERIES = {Lecture Notes in Computer Science},
VOL={3142},
PUBLISHER={Springer},
}

@techreport{BKK05,
title={Focused sampling: {C}omputing topical web statistics},
author={Z. Bar-Yossef and R. Krauthgamer and T. Kanungo},
institution={IBM},
type={Research Report},
number={RJ 10339},
month=feb,
year={2005},
}

@inproceedings{HKK04,
TITLE={Object location in realistic networks},
AUTHOR={K. Hildrum and R. Krauthgamer and J. Kubiatowicz},
BOOKTITLE = {16th ACM Symposium on Parallelism in Algorithms and Architectures},
PAGES = {25--35},
YEAR = {2004},
}

@inproceedings{KL04,
title={Navigating nets: {S}imple algorithms for proximity search},
author={R. Krauthgamer and J. R. Lee},
BOOKTITLE = {15th Annual ACM-SIAM Symposium on Discrete Algorithms},
PAGES = {798--807},
YEAR = {2004},
URL = {http://dl.acm.org/citation.cfm?id=982792.982913},
}

@inproceedings{AFHKTT04,
title={Approximate classification via earthmover metrics},
author={Aaron Archer and Jittat Fakcharoenphol and Chris Harrelson and Robert Krauthgamer and Kunal Talwar and Eva Tardos},
BOOKTITLE = {15th Annual ACM-SIAM Symposium on Discrete Algorithms},
PAGES = {1072--1080},
YEAR = {2004},
URL = {http://dl.acm.org/citation.cfm?id=982792.982952},
}


@article{CGH+05,
author = {J. Chuzhoy and S. Guha and E. Halperin and S. Khanna and G. Kortsarz and R. Krauthgamer and J. Naor},
title = {Asymmetric k-center is log* n-hard to approximate},
journal = {J. ACM},
volume = {52},
number = {4},
year = {2005},
paGes = {538--551},
doi = {http://doi.acm.org/10.1145/1082036.1082038},
publisher = {ACM Press},
}

@techreport{HKK03,
title={Tight lower bounds for the asymmetric $k$-center problem},
author={E.~Halperin and G.~Kortsarz and R.~Krauthgamer},
institution={Electronic Colloquium on Computational Complexity},
type = "ECCC Report",
number = "TR03-032",
year = "2003",
}

@inproceedings{GKL03,
title={Bounded geometries, fractals, and low-distortion embeddings},
author={A. Gupta and R. Krauthgamer and J. R. Lee},
booktitle = {44th Annual IEEE Symposium on Foundations of Computer Science},
pages={534-543},
year=2003,
doi={10.1109/SFCS.2003.1238226},
}

@inproceedings{HBKKW03,
author={E. Halperin and J. Buhler and R. Karp and R. Krauthgamer and B. Westover},
booktitle={11th Conference on Intelligent Systems for Molecular Biology},
pages={122--129},
year=2003,
}

@inproceedings{AKR03,
author={E. Amir and R. Krauthgamer and S. Rao},
title={Constant factor approximation of vertex-cuts in planar graphs},
booktitle={35th ACM Symposium on Theory of Computing},
pages={90--99},
year={2003},
doi={10.1145/780542.780557},
}

@article {KL07,
AUTHOR = {Krauthgamer, R. and Lee, J. R.},
TITLE = {The intrinsic dimensionality of graphs},
JOURNAL = {Combinatorica},
VOLUME = {27},
YEAR = {2007},
NUMBER = {5},
PAGES = {551--585},
}

@inproceedings{KL03,
author={R. Krauthgamer and J. R. Lee},
title={The intrinsic dimensionality of graphs},
booktitle={Proceedings of the 35th ACM Symposium on Theory of Computing},
pages={438--447},
year={2003}
}

@inproceedings{HK03,
title={Polylogarithmic inapproximability},
author={E. Halperin and R. Krauthgamer},
booktitle={Proceedings of the 35th ACM Symposium on Theory of Computing},
pages={585--594},
year={2003}
}


@article{HKKSW07,
author = {E. Halperin and G. Kortsarz and R. Krauthgamer and A. Srinivasan and N. Wang},
title = {Integrality Ratio for Group Steiner Trees and Directed Steiner Trees},
publisher = {SIAM},
year = {2007},
journal = {SIAM Journal on Computing},
volume = {36},
number = {5},
pages = {1494-1511},
doi = {10.1137/S0097539704445718}
}

@inproceedings{HKKSW03,
title={Integrality ratio for Group {S}teiner Trees and Directed {S}teiner Trees},
author={E. Halperin and G. Kortsarz and R. Krauthgamer and A. Srinivasan and N. Wang},
BOOKTITLE = {14th Annual ACM-SIAM Symposium on Discrete Algorithms},
PAGES = {275--284},
YEAR = {2003},
url = {http://dl.acm.org/citation.cfm?id=644108.644155},
}

@inproceedings{KS03,
title={Property testing of data dimensionality},
author={R. Krauthgamer and O. Sasson},
BOOKTITLE = {14th Annual ACM-SIAM Symposium on Discrete Algorithms},
PAGES = {18--27},
YEAR = {2003},
url = {http://dl.acm.org/citation.cfm?id=644108.644112},
}

@article{KKL04,
AUTHOR = {Kortsarz, G. and Krauthgamer, R. and Lee, J. R.},
TITLE = {Hardness of approximation for vertex-connectivity network design problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {3},
PAGES = {704--720},
YEAR = {2004},
}

@incollection {KKL02,
AUTHOR = {Kortsarz, G. and Krauthgamer, R. and Lee, J. R.},
TITLE = {Hardness of approximation for vertex-connectivity network design problems},
BOOKTITLE = {5th International workshop on Approximation algorithms for combinatorial optimization (APPROX)},
PAGES = {185--199},
PUBLISHER = {Springer},
YEAR = {2002},
}

@article{KLM04,
AUTHOR = {Krauthgamer, R. and Linial, N. and Magen, A.},
TITLE = {Metric Embeddings--Beyond One-Dimensional Distortion},
JOURNAL={Discrete \& Computational Geometry},
PUBLISHER={Springer},
VOLUME = {31},
YEAR = {2004},
NUMBER = {3},
PAGES = {339--356},
}

@techreport{KLM02,
title="Metric embeddings beyond one-dimensional distortion",
author="R. Krauthgamer and N. Linial and A. Magen",
year=2002,
institution = {UC Berkeley},
number = {CSD-02-1181},
}

@article{FK03,
TITLE="The probable value of the Lovasz-Schrijver relaxations for maximum independent set",
AUTHOR="U. Feige and R. Krauthgamer",
JOURNAL = {SIAM J. Comput.},
VOLUME = {32},
YEAR = {2003},
NUMBER = {2},
PAGES = {345--370},
DOI = {10.1137/S009753970240118X},
}

@inproceedings{HKKN01,
AUTHOR = {S. Halevi and R. Krauthgamer and E. Kushilevitz and K. Nissim},
TITLE = {Private approximation of {NP}-hard functions},
BOOKTITLE = {33rd Annual ACM Symposium on the Theory of Computing},
PAGES = {550--559},
YEAR = {2001},
}

@inproceedings{JKKSS01,
AUTHOR = {T.S. Jayram and T. Kimbrel and R. Krauthgamer and B. Schieber and M. Sviridenko},
TITLE = {Online server allocation in a server farm via benefit task systems},
BOOKTITLE = {33rd Annual ACM Symposium on the Theory of Computing},
PAGES = {540--549},
YEAR = {2001},
}

@article{KK01,
AUTHOR = {Kortsarz, G. and Krauthgamer, R.},
TITLE = {On approximating the achromatic number},
JOURNAL = {SIAM J. Discrete Math.},
VOLUME = {14},
YEAR = {2001},
NUMBER = {3},
PAGES = {408--422},
url = {http://dl.acm.org/citation.cfm?id=365411.365466},
}

@article{FK06,
author = {U. Feige and R. Krauthgamer},
title = {A Polylogarithmic Approximation of the Minimum Bisection},
publisher = {SIAM},
year = {2006},
journal = {SIAM Review},
volume = {48},
number = {1},
pages = {99-130},
doi = {10.1137/050640904},
}

@article {FK02,
AUTHOR = {Feige, U. and Krauthgamer, R.},
TITLE = {A polylogarithmic approximation of the minimum bisection},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
YEAR = {2002},
NUMBER = {4},
PAGES = {1090--1118},
}

@InProceedings{FK00:bisection2,
title="A polylogarithmic approximation of the minimum bisection",
author="U. Feige and R. Krauthgamer",
pages={105--115},
booktitle = {41st Annual IEEE Symposium on Foundations of Computer Science},
year=2000,
}

@InProceedings{FKN00:bisection,
title="Approximating the minimum bisection size",
author="U. Feige and R. Krauthgamer and K. Nissim",
pages={530--536},
booktitle={32nd Annual ACM Symposium on Theory of Computing},
year=2000,
}

@article{FKN03,
title={On cutting a few vertices from a graph},
author={U. Feige and R. Krauthgamer and K. Nissim},
journal={Discrete Applied Mathematics},
volume={127},
number={3},
pages={643--649},
year={2003},
doi = {10.1016/S0166-218X(02)00394-3},
publisher = {Elsevier},
}

@inproceedings {BKM00,
AUTHOR = {Broder, A. Z. and Krauthgamer, R. and Mitzenmacher, M.},
TITLE = {Improved classification via connectivity information},
BOOKTITLE = {11th Annual ACM-SIAM Symposium on Discrete Algorithms},
PAGES = {576--585},
YEAR = {2000},
url = {http://dl.acm.org/citation.cfm?id=338219.338610},
}

@article {FK00:HiddenClique,
AUTHOR = {Feige, U. and Krauthgamer, R.},
TITLE = {Finding and certifying a large hidden clique in a semirandom graph},
JOURNAL = {Random Structures Algorithms},
FJOURNAL = {Random Structures \& Algorithms},
VOLUME = {16},
YEAR = {2000},
NUMBER = {2},
PAGES = {195--208},
DOI = {10.1002/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A},
}

@article{FK00:livelock,
title={Networks on which hot-potato routing does not livelock},
author={U. Feige and R. Krauthgamer},
journal={Dist. Comp.},
fjournal={Distributed Computing},
pages={53--58},
year=2000,
volume=13,
number=1,
doi = {10.1007/s004460050005},
}

@inproceedings {FK97,
author = {U. Feige and R. Krauthgamer},
title = {Stereoscopic Families of Permutations, and their Applications},
booktitle = {5th Israel Symposium on the Theory of Computing and Systems},
pages = {85--95},
year = {1997},
}