Online Publications of Robert Krauthgamer

• Please read the copyright notice.
• I annotated papers with the following (partial) keywords:
  • AA = Analysis of Algorithms
  • CC = Computational Complexity
  • ME = Metric Spaces and Embeddings
  • WWW = Web-related
  • Note: Some papers/slides are gzipped postcript/powerpoint files.
• See also the papers' abstracts and the papers by keyword.

Papers

1. Estimating the Sortedness of a Data Stream (AA, ME)
   Parikshit Gopalan, T. S. Jayram, Robert Krauthgamer and Ravi Kumar
   Accepted to SODA 2007.
   
2. Algorithms on negatively curved spaces (AA, ME)
   Robert Krauthgamer and James R. Lee
   To appear in FOCS 2006.
   [abstract] [conf. version: pdf]
   
3. Embedding the Ulam metric into l_1 (AA, ME)
   Robert Krauthgamer and Moses Charikar
   Accepted to Theory Of Computing.
   
4. Improved lower bounds for embeddings into L_1 (AA, ME)
   Robert Krauthgamer and Yuval Rabani
   In Proceedings of SODA 2006.
   [abstract] [bibtex] [conf. version: ps / pdf / doi] [draft of full version]
   
5. 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, 2005. Preliminary version in Proceedings of CCC 2005.
   [abstract] [bibtex] [conf. version: ps / pdf / doi] [journal version: ps / pdf / doi]
   
6. 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]
   
7. 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]
   
8. 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] [full version ps / pdf / doi / arXiv]
   
9. 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 / doi / doi]
   
10. 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]
    
11. Object location in realistic networks (AA, ME)
    Kirsten Hildrum, Robert Krauthgamer and John Kubiatowicz
    In Proceedings of SPAA 2004.
    [abstract] [bibtex] [conf. version]
    
12. 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]
13. 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]
    
14. 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]
15. 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]
16. 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]
    
17. 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]
18. The intrinsic dimensionality of graphs (ME)
    Robert Krauthgamer and James R. Lee
    Accepted to Combinatorica. Preliminary version in Proceedings of STOC'03.
    [abstract] [bibtex] [conf. version] [full version: ps / pdf] [slides: ppt / pdf]
19. Polylogarithmic inapproximability (CC)
    Eran Halperin and Robert Krauthgamer
    In Proceedings of STOC 2003.
    [abstract] [bibtex] [conf. version: ps / pdf]
20. Integrality ratio for Group Steiner Trees and Directed Steiner Trees (AA)
    Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan and Nan Wang
    Accepted to SIAM Journal on Computing, 2006.
    In 14th Symposium on Discrete Algorithms (SODA'03), pp. 275-284, January 2003.
    [abstract] [bibtex] [slides] [conf. version] [journal version: ps / pdf]
    
21. Property testing of data dimensionality (AA ,CC ,ME)
    Robert Krauthgamer and Ori Sasson
    In Proceedings of SODA 2003.
    [abstract] [bibtex] [slides] [conf. version]
    
22. 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] [James' slides] [conf. version] [journal version]
    
23. 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]
    
24. The probable value of the Lovasz-Schrijver relaxations for maximum independent set (AA)
    Uri Feige and Robert Krauthgamer
    Weizmann Institute Technical Report # MCS-02-01, January 2002.
    SIAM Journal on Computing, 32(2):345-370, 2003.
    [abstract] [bibtex] [report version] [journal version: ps / pdf] [my slides from the Bertinoro Workshop]
    
25. 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]
26. 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)]
    
27. 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]
    
28. 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]
29. 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]
30. 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]
    
31. Finding and certifying a large hidden clique in a semi-random graph (AA)
    Uri Feige and Robert Krauthgamer
    Weizmann Institute Technical Report # MCS99-04, January 1999.
    Random Structures and Algorithms 16(2): 195-208, 2000.
    [abstract] [report version] [journal version] [my slides from the Bertinoro Workshop]
    
32. Improved performance guarantees for bandwidth minimization heuristics (AA)
    Uri Feige and Robert Krauthgamer
    Unpublished manuscript, November 1998. [manuscript]
    
33. Networks on which hot-potato routing does not livelock (AA) [abstract]
    Uri Feige and Robert Krauthgamer
    Distributed Computing, 13(1):53-58 , 2000. [preprint **]
    
34. 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. [conf. version]
    

Theses

• Coping with NP-hardness: Approximating minimum bisection and heuristics for maximum clique [abstract]
  Robert Krauthgamer. Supervisor: Uri Feige.
  Ph.D. thesis, Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel. April 2001. [thesis (gzipped 349Kb)]
  
• Simple algorithms for hot-potato routing [abstract]
  Robert Krauthgamer. Supervisor: Uri Feige.
  M.Sc. thesis, Department of Applied Mathematics and Computer Science, Weizmann Institute of Science, Rehovot, Israel. October 1996. [thesis (gzipped 260Kb)]
  

Patents Pending

1. Dynamic resource allocation using projected future benefits.
   T. S. Jayram, Tracy Kimbrel, Robert Krauthgamer, Baruch Schieber and Maxim Sviridenko.
   IBM Invention Disclosure YOR8-2000-1125, filed December, 2001.
2. Dynamic resource allocation using known future benefits.
   T. S. Jayram, Tracy Kimbrel, Robert Krauthgamer, Maria Minkoff, Baruch Schieber and Maxim Sviridenko.
   IBM Invention Disclosure YOR8-1114, filed December, 2001.
3. System, method, and service for using a focused random walk to produce samples on a topic from a collection of hyper-linked pages.
   Ziv Bar-Yossef, Tapas Kanungo and Robert Krauthgamer.
   IBM Invention Disclosure ARC-920040067-US1, filed December 2004.
4. System and method for detecting matches of small edit distance.
   Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer and Ravi Kumar.
   IBM Invention Disclosure ARC-920050044-US1, filed September 2005.