Bibtex entries for Robert Krauthgamer

@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},
url = {http://doi.acm.org/10.1145/1993806.1993830},
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},
url = {http://doi.acm.org/10.1145/1993636.1993680},
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},
}

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

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

@inproceedings{GKK10,
author = {Lee-Ad Gottlieb and Leonid Kontorovich and Robert Krauthgamer},
title = {Efficient Classification for Metric Data},
pages = {433-440},
ee = {http://www.colt2010.org/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},
}

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

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

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

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

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

@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},
URL = {http://www.theoryofcomputing.org/articles/v007a005},
}

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

@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},
ee = {http://doi.ieeecomputersociety.org/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},
URL = {http://www.theoryofcomputing.org/articles/main/v002/a011},
}

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

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

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

@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 = {791--801},
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={Proceedings of the 35th ACM Symposium on Theory of Computing},
pages={90--99},
month={jun},
year={2003}
}

@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},
keywords = {group Steiner tree; directed Steiner tree; flow-based relaxation; linear programming relaxation; integrality ratio; approximation algorithms},
url = {http://link.aip.org/link/?SMJ/36/1494/1},
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},
}

@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},
url = {http://link.aip.org/link/?SIR/48/99/1},
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},
url = {http://dx.doi.org/10.1016/S0166-218X(02)00394-3},
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},
}

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

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