Robert Krauthgamer I was a postdoc at UC Berkeley's Computer Science Division and at ICSI (aka International Computer Science Institute). I appreciate them letting me keep this account active. UPDATE: As of September 2003, I am a Research Staff Member at the IBM Almaden Research Center. Here is my new contact information.

RESEARCH

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

Editorial. Theory of Computing.

Reading Group. Fall 2006 algorithms reading group

Publications. Most of my papers are available online: 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 Joseph (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

• The ICSI algorithms group and its seminars
  • ICSI theory seminars
• The (UC Berkeley) theory group and its seminars
  • Theory seminars
  • Algorithms reading group
  • Theory lunch
• Related seminars (around here)
  • EECS Joint Colloquium
  • List of upcoming CS seminars
  • Networking seminar
  • AI-Robotics-Vision seminar

Collections of Technical Work

• The Electronic Library of Mathematics
• Electronic Colloquium on Computational Complexity (ECCC)
• The Computing Research Repository (CoRR)
• Compendium of approximation results
• Collection of Lecture Notes, Surveys, and Papers
• Online Books and Lecture Notes in Mathematics

Related to Theoretical Computer Science

• TCS Virtual Address Book (or a textual version )
• Theory Net, DMANET, and comp.theory
• Theoretical Computer Science on the Web (Formerly Denis Grinberg's theory page)

Jargon problems ?

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

Other links

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