Bibtex entries for Robert Krauthgamer

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

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

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

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

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

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

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