Bibtex entries for Robert Krauthgamer

@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{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},
}

@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",
month="Nov",
day="01",
volume="79",
number="3",
pages="645--653",
issn="1432-0541",
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},
month = nov,
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 Berlin Heidelberg},
}

@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},
chapter = {20},
pages = {279-293},
doi = {10.1137/1.9781611973402.20},
ee = {http://epubs.siam.org/doi/abs/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},
chapter = {91},
pages = {1229-1243},
doi = {10.1137/1.9781611973402.91},
ee = {http://epubs.siam.org/doi/abs/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},
chapter = {77},
pages = {1029-1040},
doi = {10.1137/1.9781611973402.77},
ee = {http://epubs.siam.org/doi/abs/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 = {Proceedings of the 2012 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},
ee = {http://epubs.siam.org/doi/abs/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},
ee = {http://colt2010.haifa.il.ibm.com/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},
month = {jan},
year = 2008,
pages={343--352},
}


@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,
month={jan},
pages={809--818},
}

@article{AK10,
author = {Andoni, Alexandr and Krauthgamer, Robert},
title = {The Computational Hardness of Estimating Edit Distance},
journal = {SIAM J. Comput.},
volume = {39},
number = {6},
month = apr,
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,
month=oct,
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},
ee = {http://dx.doi.org/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},
ee = {http://dx.doi.org/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},
}

@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 Ulam 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},
ee = {http://dx.doi.org/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},
}

@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},
month=jun,
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},
}

@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,
month=oct,
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,
month=oct,
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},
MONTH = JUL,
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},
MONTH = JUN,
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},
MONTH = JAN,
YEAR = {2004},
}

@inproceedings{AFHKTT04,
title={Approximate classification via earthmover metrics},
author={A. Archer and J. Fakcharoenphol and C. Harrelson and R. Krauthgamer and K. Talwar and E. Tardos},
BOOKTITLE = {15th Annual ACM-SIAM Symposium on Discrete Algorithms},
PAGES = {1072--1080},
MONTH = JAN,
YEAR = {2004},
}


@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,
month=oct,
}

@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},
month=jun,
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},
month=jun,
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},
month={jun},
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},
MONTH = JAN,
YEAR = {2003},
}

@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},
MONTH = JAN,
YEAR = {2003},
}

@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 Comput. Geom.},
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",
month=may,
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},
MONTH = jul,
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},
MONTH = jul,
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},
}

@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,
month=nov,
}

@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,
month=may,
}

@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},
MONTH = JAN,
YEAR = {2000},
}

@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},
month = JUN,
year = {1997},
}