Bounded geometries, fractals, and low-distortion embeddings A Gupta, R Krauthgamer, JR Lee 44th Annual IEEE Symposium on Foundations of Computer Science, 2003 …, 2003 | 429 | 2003 |

Navigating nets: Simple algorithms for proximity search R Krauthgamer, JR Lee Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete …, 2004 | 374 | 2004 |

Polylogarithmic inapproximability E Halperin, R Krauthgamer Proceedings of the thirty-fifth annual ACM symposium on Theory of computing …, 2003 | 231 | 2003 |

On the hardness of approximating multicut and sparsest-cut S Chawla, R Krauthgamer, R Kumar, Y Rabani, D Sivakumar computational complexity 15 (2), 94-114, 2006 | 229 | 2006 |

Finding and certifying a large hidden clique in a semirandom graph U Feige, R Krauthgamer Random Structures & Algorithms 16 (2), 195-208, 2000 | 202 | 2000 |

A polylogarithmic approximation of the minimum bisection U Feige, R Krauthgamer SIAM Journal on Computing 31 (4), 1090-1118, 2002 | 191 | 2002 |

Measured descent: A new embedding method for finite metrics R Krauthgamer, JR Lee, M Mendel, A Naor 45th Annual IEEE Symposium on Foundations of Computer Science, 434-443, 2004 | 165 | 2004 |

Approximating edit distance efficiently Z Bar-Yossef, TS Jayram, R Krauthgamer, R Kumar 45th Annual IEEE Symposium on Foundations of Computer Science, 550-559, 2004 | 145 | 2004 |

Partitioning graphs into balanced components R Krauthgamer, J Naor, R Schwartz Proceedings of the twentieth annual ACM-SIAM symposium on Discrete …, 2009 | 119 | 2009 |

How hard is it to approximate the best Nash equilibrium? E Hazan, R Krauthgamer SIAM Journal on Computing 40 (1), 79-91, 2011 | 114 | 2011 |

Hardness of approximation for vertex-connectivity network design problems G Kortsarz, R Krauthgamer, JR Lee SIAM Journal on Computing 33 (3), 704-720, 2004 | 111 | 2004 |

Algorithms on negatively curved spaces R Krauthgamer, JR Lee 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06 …, 2006 | 106 | 2006 |

Improved Lower Bounds for Embeddings into R Krauthgamer, Y Rabani SIAM Journal on Computing 38 (6), 2487-2498, 2009 | 104 | 2009 |

Polylogarithmic approximation for edit distance and the asymmetric query complexity A Andoni, R Krauthgamer, K Onak 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 377-386, 2010 | 98 | 2010 |

Fault-tolerant spanners: better and simpler M Dinitz, R Krauthgamer Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of …, 2011 | 85 | 2011 |

The probable value of the Lovász--Schrijver relaxations for maximum independent set U Feige, R Krauthgamer SIAM Journal on Computing 32 (2), 345-370, 2003 | 84 | 2003 |

Min-max graph partitioning and small set expansion N Bansal, U Feige, R Krauthgamer, K Makarychev, V Nagarajan, J Seffi, ... SIAM Journal on Computing 43 (2), 872-904, 2014 | 83 | 2014 |

Earth mover distance over high-dimensional spaces. A Andoni, P Indyk, R Krauthgamer SODA 8, 343-352, 2008 | 81 | 2008 |

Streaming algorithms via precision sampling A Andoni, R Krauthgamer, K Onak 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, 363-372, 2011 | 78 | 2011 |

Asymmetric *k*-center is log^{*} *n*-hard to approximateJ Chuzhoy, S Guha, E Halperin, S Khanna, G Kortsarz, R Krauthgamer, ... Journal of the ACM (JACM) 52 (4), 538-551, 2005 | 75 | 2005 |