Publications of Robert Krauthgamer by keyword

Analysis of Algorithms

1. The Query Complexity of Edit Distance (ME, AA)
   Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak
   Manuscript, November 2009.
   
2. Partitioning Graphs into Balanced Components (AA, ME)
   Robert Krauthgamer, Joseph (Seffi) Naor, and Roy Schwartz
   In Proceedings of SODA 2009.
   [abstract] [bibtex] [conf. version: pdf / doi]
   
3. Approximate Line Nearest Neighbor in High Dimensions (AA, ME)
   Alexandr Andoni, Piotr Indyk, Robert Krauthgamer, and Huy L. Nguyen
   In Proceedings of SODA 2009.
   [abstract] [bibtex] [conf. version: pdf / doi]
   
4. Overcoming the l_1 non-embeddability barrier: Algorithms for product metrics (AA, ME)
   Alexandr Andoni, Piotr Indyk and Robert Krauthgamer
   In Proceedings of SODA 2009.
   [abstract] [bibtex] [conf. version: pdf / doi] [slides]
   
5. The Smoothed Complexity of Edit Distance (AA)
   Alexandr Andoni and Robert Krauthgamer
   In Proceedings of ICALP 2008.
   [abstract] [bibtex] [conf. version: pdf / doi] [draft of full version]
   
6. Distance Estimation Revisited: Drawing a Computational View of Embeddings (AA, CC, ME)
   Alexandr Andoni and Robert Krauthgamer
   Manuscript, July 2007.
   
7. Metric Clustering via Consistent Labeling (AA, ME)
   Robert Krauthgamer and Tim Roughgarden
   In Proceedings of SODA 2008.
   [abstract] [bibtex] [conf. version: pdf / doi] [draft of full version]
   
8. The Computational Hardness of Estimating Edit Distance (AA, CC, ME)
   Alexandr Andoni and Robert Krauthgamer
   Invited to special issue of SIAM Journal on Computing. Preliminary version in FOCS 2007.
   [abstract] [bibtex] [conf. version: pdf / doi] [draft of full version] [slides]
   
9. Earth Mover Distance over High-Dimensional Spaces (AA, ME)
   Alexandr Andoni, Piotr Indyk and Robert Krauthgamer
   In Proceedings of SODA 2008. Previously as ECCC Report TR07-04, April 2007.
   [abstract] [bibtex] [report version: pdf] [conf. version: pdf / doi]
   
10. Greedy list intersection (AA)
    Robert Krauthgamer, Aranyak Mehta, Vijayshankar Raman, and Atri Rudra
    In Proceedings of ICDE 2008.
    [abstract] [bibtex] [conf. version: pdf / doi]
    
11. Pricing commodities, or how to sell when buyers have restricted valuations (AA)
    Robert Krauthgamer, Aranyak Mehta, and Atri Rudra
    Invited to a special issue of Theoretical Computer Science (TCS), 2007. Preliminary version in Proceedings of WAOA 2007.
    [abstract] [bibtex] [conf. version: pdf / doi] [journal version: pdf / doi]
    
12. On triangulation of simple networks (AA, ME)
    Robert Krauthgamer
    In Proceedings of SPAA 2007.
    [abstract] [bibtex] [conf. version: pdf / doi]
    
13. Estimating the Sortedness of a Data Stream (AA, CC)
    Parikshit Gopalan, T. S. Jayram, Robert Krauthgamer and Ravi Kumar
    In Proceedings of SODA 2007.
    [abstract] [bibtex] [conf. version: pdf / doi]
    
14. Algorithms on negatively curved spaces (AA, ME)
    Robert Krauthgamer and James R. Lee
    In Proceedings of FOCS 2006.
    [abstract] [bibtex] [conf. version: pdf / doi]
    
15. Embedding the Ulam metric into l_1 (AA, ME)
    Moses Charikar and Robert Krauthgamer
    Theory of Computing (ToC), 2006.
    [abstract] [bibtex] [journal version: ps / pdf / url]
    
16. Improved lower bounds for embeddings into L_1 (AA, ME)
    Robert Krauthgamer and Yuval Rabani
    SIAM Journal on Computing, 2009. Preliminary version in Proceedings of SODA 2006.
    [abstract] [bibtex] [conf. version: ps / pdf / doi] [journal version: pdf / doi]
    
17. The sketching complexity of pattern matching (AA, CC)
    Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer and Ravi Kumar
    In Proceedings of RANDOM 2004.
    [abstract] [bibtex] [conf. version: ps / pdf / doi]
    
18. Approximating edit distance efficiently (AA, ME)
    Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer and Ravi Kumar
    In Proceedings of FOCS 2004.
    [abstract] [bibtex] [conf. version: ps / pdf / doi]
    
19. The black-box complexity of nearest neighbor search (AA, ME)
    Robert Krauthgamer and James R. Lee
    Invited to a special issue of Theoretical Computer Science (TCS), 2005. Preliminary version in Proceedings of ICALP 2004.
    [abstract] [bibtex] [conf. version] [journal version: ps / pdf / doi]
    
20. Object location in realistic networks (AA, ME)
    Kirsten Hildrum, Robert Krauthgamer and John Kubiatowicz
    In Proceedings of SPAA 2004.
    [abstract] [bibtex] [conf. version: ps / pdf]
    
21. Navigating nets: Simple algorithms for proximity search (AA, ME)
    Robert Krauthgamer and James R. Lee
    In Proceedings of SODA 2004.
    [abstract] [bibtex] [conf. version: ps / pdf] [slides]
22. Approximate classification via earthmover metrics (AA, ME)
    Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, and Eva Tardos
    In Proceedings of SODA 2004.
    [abstract] [bibtex] [conf. version]
    
23. Bounded geometries, fractals, and low-distortion embeddings (AA ,ME)
    Anupam Gupta, Robert Krauthgamer and James R. Lee
    In Proceedings of FOCS 2003.
    [abstract] [bibtex] [conf. version]
24. Detecting protein sequence conservation via metric embeddings [abstract] [EMBED project] (AA ,ME)
    Eran Halperin, Jeremy Buhler, Richard Karp, Robert Krauthgamer and Ben Westover
    In 11th Conference on Intelligent Systems for Molecular Biology (ISMB 2003), pp. 122-129, June 2003. [conf. version]
    
25. Constant factor approximation of vertex-cuts in planar graphs (AA)
    Eyal Amir, Robert Krauthgamer and Satish Rao
    In Proceedings of STOC 2003.
    [abstract] [bibtex] [conf. version: ps / pdf / doi]
26. Integrality ratio for Group Steiner Trees and Directed Steiner Trees (AA)
    Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan and Nan Wang
    SIAM Journal on Computing, 2007. Preliminary version in Proceedings of SODA'03.
    [abstract] [bibtex] [slides] [conf. version] [journal version: ps / pdf / doi]
    
27. Property testing of data dimensionality (AA ,CC ,ME)
    Robert Krauthgamer and Ori Sasson
    In Proceedings of SODA 2003.
    [abstract] [bibtex] [slides] [conf. version]
    
28. The probable value of the Lovasz-Schrijver relaxations for maximum independent set (AA)
    Uri Feige and Robert Krauthgamer
    SIAM Journal on Computing, 32(2):345-370, 2003. Previously as Weizmann Institute Technical Report # MCS-02-01, January 2002.
    [abstract] [bibtex] [report version] [journal version: ps / pdf] [my slides from the Bertinoro Workshop]
    
29. Online server allocation in a server farm via benefit task systems (AA ,WWW)
    T. S. Jayram, Tracy Kimbrel, Robert Krauthgamer, Baruch Schieber and Maxim Sviridenko.
    In Proceedings of STOC 2001.
    [abstract] [bibtex] [conf. version: ps pdf] [slides: ppt pdf)]
    
30. On approximating the achromatic number (AA ,CC)
    Guy Kortsarz and Robert Krauthgamer
    In 12th Symposium on Discrete Algorithms (SODA'01), pp. 309-318, January 2001.
    SIAM Journal on Discrete Mathematics, 2001.
    [abstract] [bibtex] [conf. version] [full version]
    
31. A polylogarithmic approximation of the minimum bisection (AA)
    Uri Feige and Robert Krauthgamer
    SIAM Journal on Computing, 2002. Preliminary version in Proceedings of FOCS '00.
    Awarded the SIAM Outstanding Paper Prize in July 2005.
    Invited to SIAM Review (SIGEST section), 2006.
    [abstract] [bibtex] [conf. version] [journal version] [further expanded version: ps / pdf / doi] [slides]
32. Approximating the minimum bisection size (AA) [abstract]
    Uri Feige, Robert Krauthgamer and Kobbi Nissim
    In 32nd Symposium on Theory of Computing (STOC '00), pp. 530-536, May 2000. [conf. version]
    A journal version for some results from this paper:
    • On cutting a few vertices from a graph [abstract]
      Discrete Applied Mathematics, 127(3): 643-649, 2003. [journal version]
33. Improved classification via connectivity information (AA ,WWW) [abstract]
    Andrei Broder, Robert Krauthgamer and Michael Mitzenmacher.
    In 11th Symposium of Discrete Algorithms (SODA '00), pp. 576-585, January 2000. [conf. version]
    
34. Finding and certifying a large hidden clique in a semi-random graph (AA)
    Uri Feige and Robert Krauthgamer
    Random Structures and Algorithms 16(2): 195-208, 2000. Previously as Weizmann Institute Technical Report # MCS99-04, January 1999.
    [abstract] [report version] [journal version] [my slides from the Bertinoro Workshop]
    
35. Improved performance guarantees for bandwidth minimization heuristics (AA)
    Uri Feige and Robert Krauthgamer
    Unpublished manuscript, November 1998. [manuscript]
    
36. Networks on which hot-potato routing does not livelock (AA) [abstract]
    Uri Feige and Robert Krauthgamer
    Distributed Computing, 13(1):53-58 , 2000. [preprint **]
    
37. Stereoscopic families of permutations, and their applications (AA ,ME) [abstract]
    Uri Feige and Robert Krauthgamer
    In 5th Israel Symposium on the Theory of Computing and Systems (ISTCS '97), pp. 85-95, June 1997.
    [abstract] [bibtex] [conf. version: ps / pdf / doi]
    

Computational Complexity

1. How hard is it to approximate the best Nash equilibrium? (CC)
   Elad Hazan and Robert Krauthgamer
   In Proceedings of SODA 2009.
   [abstract] [bibtex] [conf. version: pdf / doi] [draft of full version]
   
2. Distance Estimation Revisited: Drawing a Computational View of Embeddings (AA, CC, ME)
   Alexandr Andoni and Robert Krauthgamer
   Manuscript, July 2007.
   
3. The Computational Hardness of Estimating Edit Distance (AA, CC, ME)
   Alexandr Andoni and Robert Krauthgamer
   Invited to special issue of SIAM Journal on Computing. Preliminary version in FOCS 2007.
   [abstract] [bibtex] [conf. version: pdf / doi] [draft of full version] [slides]
   
4. Earth Mover Distance over High-Dimensional Spaces (AA, ME)
   Alexandr Andoni, Piotr Indyk and Robert Krauthgamer
   In Proceedings of SODA 2008. Previously as ECCC Report TR07-04, April 2007.
   [abstract] [bibtex] [report version: pdf] [conf. version: pdf / doi]
   
5. Estimating the Sortedness of a Data Stream (AA, CC)
   Parikshit Gopalan, T. S. Jayram, Robert Krauthgamer and Ravi Kumar
   In Proceedings of SODA 2007.
   [abstract] [bibtex] [conf. version: pdf / doi]
   
6. On the hardness of approximating multicut and sparsest-cut (CC)
   Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, and D. Sivakumar
   Invited to special issue of Computational Complexity, 2006. Preliminary version in Proceedings of CCC 2005.
   [abstract] [bibtex] [conf. version: ps / pdf / doi] [journal version: ps / pdf / doi]
   
7. The sketching complexity of pattern matching (AA, CC)
   Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer and Ravi Kumar
   In Proceedings of RANDOM 2004.
   [abstract] [bibtex] [conf. version: ps / pdf / doi]
   
8. Asymmetric k-center is log^*n-hard to Approximate (CC)
   Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Robert Krauthgamer, and Joseph (Seffi) Naor
   Journal of the ACM, 2005. Preliminary version in ECCC Report TR03-035, May 2003.
   [abstract] [bibtex] [report version] [journal version: ps / pdf]
9. Polylogarithmic inapproximability (CC)
   Eran Halperin and Robert Krauthgamer
   In Proceedings of STOC 2003.
   [abstract] [bibtex] [conf. version: ps / pdf]
10. Property testing of data dimensionality (AA ,CC ,ME)
    Robert Krauthgamer and Ori Sasson
    In Proceedings of SODA 2003.
    [abstract] [bibtex] [slides] [conf. version]
    
11. Hardness of approximation for vertex-connectivity network design problems (CC)
    Guy Kortsarz, Robert Krauthgamer, and James R. Lee
    SIAM Journal on Computing, 2004. Preliminary version in Proceedings of APPROX 2002.
    [abstract] [bibtex] [conf. version] [journal version]
    
12. Private approximation of NP-hard functions (CC)
    Shai Halevi, Robert Krauthgamer, Eyal Kushilevitz and Kobbi Nissim
    In 33rd Symposium on Theory of Computing (STOC '01), pp. 550-559, July 2001.
    [abstract] [bibtex] [conf. version]
13. On approximating the achromatic number (AA ,CC)
    Guy Kortsarz and Robert Krauthgamer
    In 12th Symposium on Discrete Algorithms (SODA'01), pp. 309-318, January 2001.
    SIAM Journal on Discrete Mathematics, 2001.
    [abstract] [bibtex] [conf. version] [full version]
    

Metric Spaces and Embeddings

1. The Query Complexity of Edit Distance (ME, AA)
   Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak
   Manuscript, November 2009.
   
2. A Nonlinear Approach to Dimension Reduction (ME)
   Lee-Ad Gottlieb and Robert Krauthgamer
   Manuscript, July 2009.
   [abstract] [full version on the arXiv]
   
3. Partitioning Graphs into Balanced Components (AA, ME)
   Robert Krauthgamer, Joseph (Seffi) Naor, and Roy Schwartz
   In Proceedings of SODA 2009.
   [abstract] [bibtex] [conf. version: pdf / doi]
   
4. Approximate Line Nearest Neighbor in High Dimensions (AA, ME)
   Alexandr Andoni, Piotr Indyk, Robert Krauthgamer, and Huy L. Nguyen
   In Proceedings of SODA 2009.
   [abstract] [bibtex] [conf. version: pdf / doi]
   
5. Overcoming the l_1 non-embeddability barrier: Algorithms for product metrics (AA, ME)
   Alexandr Andoni, Piotr Indyk and Robert Krauthgamer
   In Proceedings of SODA 2009.
   [abstract] [bibtex] [conf. version: pdf / doi] [slides]
   
6. Distance Estimation Revisited: Drawing a Computational View of Embeddings (AA, CC, ME)
   Alexandr Andoni and Robert Krauthgamer
   Manuscript, July 2007.
   
7. Metric Clustering via Consistent Labeling (AA, ME)
   Robert Krauthgamer and Tim Roughgarden
   In Proceedings of SODA 2008.
   [abstract] [bibtex] [conf. version: pdf / doi] [draft of full version]
   
8. The Computational Hardness of Estimating Edit Distance (AA, CC, ME)
   Alexandr Andoni and Robert Krauthgamer
   Invited to special issue of SIAM Journal on Computing. Preliminary version in FOCS 2007.
   [abstract] [bibtex] [conf. version: pdf / doi] [draft of full version] [slides]
   
9. Earth Mover Distance over High-Dimensional Spaces (AA, ME)
   Alexandr Andoni, Piotr Indyk and Robert Krauthgamer
   In Proceedings of SODA 2008. Previously as ECCC Report TR07-04, April 2007.
   [abstract] [bibtex] [report version: pdf] [conf. version: pdf / doi]
   
10. On triangulation of simple networks (AA, ME)
    Robert Krauthgamer
    In Proceedings of SPAA 2007.
    [abstract] [bibtex] [conf. version: pdf / doi]
    
11. Algorithms on negatively curved spaces (AA, ME)
    Robert Krauthgamer and James R. Lee
    In Proceedings of FOCS 2006.
    [abstract] [bibtex] [conf. version: pdf / doi]
    
12. Embedding the Ulam metric into l_1 (AA, ME)
    Moses Charikar and Robert Krauthgamer
    Theory of Computing (ToC), 2006.
    [abstract] [bibtex] [journal version: ps / pdf / url]
    
13. Improved lower bounds for embeddings into L_1 (AA, ME)
    Robert Krauthgamer and Yuval Rabani
    SIAM Journal on Computing, 2009. Preliminary version in Proceedings of SODA 2006.
    [abstract] [bibtex] [conf. version: ps / pdf / doi] [journal version: pdf / doi]
    
14. Approximating edit distance efficiently (AA, ME)
    Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer and Ravi Kumar
    In Proceedings of FOCS 2004.
    [abstract] [bibtex] [conf. version: ps / pdf / doi]
    
15. Measured descent: A new embedding method for finite metrics (ME)
    Robert Krauthgamer, James R. Lee, Manor Mendel and Assaf Naor
    Geometric and Functional Analysis (GAFA), 2005. Preliminary version in Proceedings of FOCS 2004.
    [abstract] [bibtex] [conf. version: ps / pdf / doi] [journal version: ps / pdf / doi / arXiv]
    
16. The black-box complexity of nearest neighbor search (AA, ME)
    Robert Krauthgamer and James R. Lee
    Invited to a special issue of Theoretical Computer Science (TCS), 2005. Preliminary version in Proceedings of ICALP 2004.
    [abstract] [bibtex] [conf. version] [journal version: ps / pdf / doi]
    
17. Object location in realistic networks (AA, ME)
    Kirsten Hildrum, Robert Krauthgamer and John Kubiatowicz
    In Proceedings of SPAA 2004.
    [abstract] [bibtex] [conf. version: ps / pdf]
    
18. Navigating nets: Simple algorithms for proximity search (AA, ME)
    Robert Krauthgamer and James R. Lee
    In Proceedings of SODA 2004.
    [abstract] [bibtex] [conf. version: ps / pdf] [slides]
19. Approximate classification via earthmover metrics (AA, ME)
    Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, and Eva Tardos
    In Proceedings of SODA 2004.
    [abstract] [bibtex] [conf. version]
    
20. Bounded geometries, fractals, and low-distortion embeddings (AA ,ME)
    Anupam Gupta, Robert Krauthgamer and James R. Lee
    In Proceedings of FOCS 2003.
    [abstract] [bibtex] [conf. version]
21. Detecting protein sequence conservation via metric embeddings [abstract] [EMBED project] (AA ,ME)
    Eran Halperin, Jeremy Buhler, Richard Karp, Robert Krauthgamer and Ben Westover
    In 11th Conference on Intelligent Systems for Molecular Biology (ISMB 2003), pp. 122-129, June 2003. [conf. version]
    
22. The intrinsic dimensionality of graphs (ME)
    Robert Krauthgamer and James R. Lee
    Combinatorica, 2007. Preliminary version in Proceedings of STOC 2003.
    [abstract] [bibtex] [conf. version] [journal version: ps / pdf / doi] [slides: ppt / pdf]
23. Property testing of data dimensionality (AA ,CC ,ME)
    Robert Krauthgamer and Ori Sasson
    In Proceedings of SODA 2003.
    [abstract] [bibtex] [slides] [conf. version]
    
24. Metric embeddings -- beyond one-dimensional distortion (ME)
    Robert Krauthgamer, Nati Linial and Avner Magen
    In Discrete and Computational Geometry 31(3):339-356, 2004. (Earlier version in UC Berkeley Technical Report #CSD-02-1181, May 2002.)
    [abstract] [bibtex] [report version] [journal version]
    
25. Stereoscopic families of permutations, and their applications (AA ,ME) [abstract]
    Uri Feige and Robert Krauthgamer
    In 5th Israel Symposium on the Theory of Computing and Systems (ISTCS '97), pp. 85-95, June 1997.
    [abstract] [bibtex] [conf. version: ps / pdf / doi]
    

Web-related

1. Focused Sampling: Computing Topical Web Statistics (WWW)
   Ziv Bar-Yossef, Robert Krauthgamer, and Tapas Kanungo
   IBM Research Report RJ 10339, February 2005.
   [abstract] [bibtex] [report version]
   
2. Online server allocation in a server farm via benefit task systems (AA ,WWW)
   T. S. Jayram, Tracy Kimbrel, Robert Krauthgamer, Baruch Schieber and Maxim Sviridenko.
   In Proceedings of STOC 2001.
   [abstract] [bibtex] [conf. version: ps pdf] [slides: ppt pdf)]
   
3. Improved classification via connectivity information (AA ,WWW) [abstract]
   Andrei Broder, Robert Krauthgamer and Michael Mitzenmacher.
   In 11th Symposium of Discrete Algorithms (SODA '00), pp. 576-585, January 2000. [conf. version]