@InProceedings{JKS24,
@InProceedings{CGJKV24,
@InProceedings{KK24,
@InProceedings{BKKS23,
@inproceedings{CJK23,
@InProceedings{CDK23,
@InProceedings{GKKS23,
@InProceedings{AKN24,
@inproceedings{KM23,
@inproceedings{BCJKSTW22,
@inproceedings{CJKVY22,
@article{KS23,
@inproceedings{AKLPST22,
@inproceedings{GKKS22,
@inproceedings{CKZ22,
@inproceedings{AKT22,
@inproceedings{BJKW21,
@Inproceedings{AKT21c,
@Inproceedings{KKTY21b,
@article{JKLY24,
@InProceedings{CDK21,
@article{CJKV24,
@InProceedings{BKKS21,
@article{KS22,
@article{AKN22,
@inproceedings{AKT21b,
@inproceedings{KKTY21,
@inproceedings{CDK21,
@inproceedings{AKT20,
@inproceedings{BJKW21,
@article{AKT21,
@inproceedings{AKT20,
@article{BKY22,
@article{FGK24,
@inproceedings{FGK20,
@inproceedings{BKKS20,
@inproceedings{BBHJKW20,
@article{GKR22,
@Inproceedings{GKS19,
@article{AKN20,
@article{KR22,
@InProceedings{BJKW19,
@InProceedings{AKP19,
@InProceedings{FKT19,
@inproceedings{KLR19,
@InProceedings{AGIKPTUW19,
@InProceedings{KT19,
@article{KT18,
@InProceedings{KT17,
@InProceedings{CKK16,
@article{FK17,
@InProceedings{BCKLWY18,
@InProceedings{KK16,
@inproceedings{BBCKY17,
@article{DGK17,
@InProceedings{DKW15,
@InProceedings{ACKW15,
@article{KK17,
@inproceedings{AKR15,
@inproceedings{KK15,
@article{KW16,
@inproceedings{AAKK14,
@inproceedings{ACKQWZ16,
@incollection{KKPS14,
@incollection{AFKRS14,
@article{KNV15,
@article{KKN15,
@inproceedings{KKN14,
@article{GKK16,
@incollection{GKK13b,
@inproceedings{KR13,
@inproceedings{CDK12,
@inproceedings{KZ12,
@inproceedings{BGK12,
@article{GKK17,
@incollection{GKK13a,
@article{BFKMNNS14,
@inproceedings{BFKMNNS11,
@inproceedings{AKO11,
@inproceedings{DK11b,
@inproceedings{DK11a,
@inproceedings{CKR10,
@article{EGKRTT14,
@inproceedings{EGKRTT10,
@article{GK13,
@inproceedings{GK10,
@article{GKK14,
@inproceedings{GKK10,
@inproceedings{AKO10,
@inproceedings{GK11,
@inproceedings{KMRR07,
@inproceedings{Kra07,
@inproceedings{GJKK07,
@inproceedings{KL06,
@article{CK06,
@inproceedings{KR06,
@article{CKKRS06,
@inproceedings{CKKRS05,
@inproceedings{KLMN04,
@article{KLM04,
@article{FK06,
@article {FK02,
@InProceedings{FK00:bisection2,
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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",
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
author = {Moses Charikar and Robert Krauthgamer},
title = {Embedding the {U}lam metric into $\ell_1$},
journal = {Theory of Computing},
year = {2006},
number = {11},
pages = {207--224},
publisher = {Theory of Computing},
eprint = {toc:v002/a011},
doi = {10.4086/toc.2006.v002a011},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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,
}