Robert Krauthgamer Research Staff Member IBM Almaden Research Center Computer Science Principles and Methodologies Department UPDATE: I am currently in Israel; please see my Weizmann webpage. Jump to: Research ~ Useful links ~ Contact information

RESEARCH

Program Committees. APPROX 2003, STOC 2004, RANDOM 2005, STOC 2007, APPROX 2007.

Editorial. Theory of Computing.

Publications. Most of my papers are available online (from my Weizmann homepage): Chronologically or by keyword.

Selected publications:

• A polylogarithmic approximation of the minimum bisection. Uri Feige and Robert Krauthgamer. SIAM Journal on Computing, 2002. Preliminary version in Proc. of FOCS 2000. Awarded the SIAM Outstanding Paper Prize in July 2005. Invited to SIAM Review, SIGEST section, To appear.
• The probable value of the Lovasz-Schrijver relaxations for maximum independent set. Uri Feige and Robert Krauthgamer. SIAM Journal on Computing, 2003.
• Polylogarithmic inapproximability. Eran Halperin and Robert Krauthgamer. In Proc. of STOC 2003.
• Asymmetric k-center is log^*n-hard to Approximate. Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Robert Krauthgamer, and Jo seph (Seffi) Naor. Journal of the ACM, 2005.
• The intrinsic dimensionality of graphs. Robert Krauthgamer and James R. Lee. In Proc. of STOC 2003.
• Navigating nets: Simple algorithms for proximity search. Robert Krauthgamer and James R. Lee. In Proc. of SODA 2004.
• Measured descent: A new embedding method for finite metrics. Robert Krauthgamer, James R. Lee, Manor Mendel and Assaf Naor. Geometric and Functional Analysis, 2005. Preliminary version in Proc. of FOCS 2004.
• Approximating edit distance efficiently. Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer and Ravi Kumar. In Proc. of FOCS 2004.
• On the hardness of approximating multicut and sparsest-cut. Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, and D. Sivakumar. Invited to special issue of Computational Complexity. Preliminary version in Proc. of CCC 2005.

USEFUL LINKS

• TCS Virtual Address Book (or a textual version )
• Theory Net, DMANET, and comp.theory
• Compendium of approximation results
• Theoretical Computer Science on the Web (Formerly Denis Grinberg's theory page)
• Electronic Colloquium on Computational Complexity (ECCC)
• Collection of Lecture Notes, Surveys, and Papers
• Online Books and Lecture Notes in Mathematics

Jargon problems?

• On-line Dictionary of Computing
• Mathematical Programming GlossaryŠ

Other

• Tips for authors and Three Sins of Authors in Computer Science and Math.
• TOM document conversion service

CONTACT INFORMATION

  Privacy | Legal | Contact | IBM Home | Research Home | Project List | Research Sites