Robert Krauthgamer
Robert Krauthgamer
Verified email at weizmann.ac.il - Homepage
Title
Cited by
Cited by
Year
Bounded geometries, fractals, and low-distortion embeddings
A Gupta, R Krauthgamer, JR Lee
44th Annual IEEE Symposium on Foundations of Computer Science, 2003 …, 2003
4202003
Navigating nets: simple algorithms for proximity search
R Krauthgamer, JR Lee
Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete …, 2004
3572004
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
2312006
Polylogarithmic inapproximability
E Halperin, R Krauthgamer
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing …, 2003
2302003
Finding and certifying a large hidden clique in a semirandom graph
U Feige, R Krauthgamer
Random Structures & Algorithms 16 (2), 195-208, 2000
1972000
A polylogarithmic approximation of the minimum bisection
U Feige, R Krauthgamer
SIAM Journal on Computing 31 (4), 1090-1118, 2002
1862002
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
1642004
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
1372004
How hard is it to approximate the best Nash equilibrium?
E Hazan, R Krauthgamer
SIAM Journal on Computing 40 (1), 79-91, 2011
1122011
Partitioning graphs into balanced components
R Krauthgamer, J Naor, R Schwartz
Proceedings of the twentieth annual ACM-SIAM symposium on Discrete …, 2009
1092009
Algorithms on negatively curved spaces
R Krauthgamer, JR Lee
2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06 …, 2006
1062006
Hardness of approximation for vertex-connectivity network design problems
G Kortsarz, R Krauthgamer, JR Lee
SIAM Journal on Computing 33 (3), 704-720, 2004
1062004
Improved Lower Bounds for Embeddings into
R Krauthgamer, Y Rabani
SIAM Journal on Computing 38 (6), 2487-2498, 2009
1002009
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
912010
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
832003
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
822014
Fault-tolerant spanners: better and simpler
M Dinitz, R Krauthgamer
Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of …, 2011
782011
Streaming algorithms via precision sampling
A Andoni, R Krauthgamer, K Onak
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, 363-372, 2011
762011
Asymmetric k-center is log* n-hard to approximate
J Chuzhoy, S Guha, E Halperin, S Khanna, G Kortsarz, R Krauthgamer, ...
Journal of the ACM (JACM) 52 (4), 538-551, 2005
752005
Dynamic resource allocation using known future benefits
TJ Kimbrel, R Krauthgamer, BM Schieber, MI Sviridenko, JS Thathachar, ...
US Patent 7,085,837, 2006
732006
The system can't perform the operation now. Try again later.
Articles 1–20