The SCEAS System
Navigation Menu

Search the dblp DataBase

Title:
Author:

Robert Krauthgamer: [Publications] [Author Rank by year] [Co-authors] [Prefers] [Cites] [Cited by]

Publications of Author

  1. Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer, Ravi Kumar
    The Sketching Complexity of Pattern Matching. [Citation Graph (0, 0)][DBLP]
    APPROX-RANDOM, 2004, pp:261-272 [Conf]
  2. Guy Kortsarz, Robert Krauthgamer, James R. Lee
    Hardness of Approximation for Vertex-Connectivity Network-Design Problems. [Citation Graph (0, 0)][DBLP]
    APPROX, 2002, pp:185-199 [Conf]
  3. Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, D. Sivakumar
    On the Hardness of Approximating Multicut and Sparsest-Cut. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 2005, pp:144-153 [Conf]
  4. Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer, Ravi Kumar
    Approximating Edit Distance Efficiently. [Citation Graph (0, 0)][DBLP]
    FOCS, 2004, pp:550-559 [Conf]
  5. Uriel Feige, Robert Krauthgamer
    A polylogarithmic approximation of the minimum bisection. [Citation Graph (0, 0)][DBLP]
    FOCS, 2000, pp:105-115 [Conf]
  6. Anupam Gupta, Robert Krauthgamer, James R. Lee
    Bounded Geometries, Fractals, and Low-Distortion Embeddings. [Citation Graph (0, 0)][DBLP]
    FOCS, 2003, pp:534-543 [Conf]
  7. Robert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor
    Measured Descent: A New Embedding Method for Finite Metrics. [Citation Graph (0, 0)][DBLP]
    FOCS, 2004, pp:434-443 [Conf]
  8. Robert Krauthgamer, James R. Lee
    Algorithms on negatively curved spaces. [Citation Graph (0, 0)][DBLP]
    FOCS, 2006, pp:119-132 [Conf]
  9. Robert Krauthgamer, James R. Lee
    The Black-Box Complexity of Nearest Neighbor Search. [Citation Graph (0, 0)][DBLP]
    ICALP, 2004, pp:858-869 [Conf]
  10. Eran Halperin, Jeremy Buhler, Richard M. Karp, Robert Krauthgamer, Ben Westover
    Detecting protein sequence conservation via metric embeddings. [Citation Graph (0, 0)][DBLP]
    ISMB (Supplement of Bioinformatics), 2003, pp:122-129 [Conf]
  11. Uriel Feige, Robert Krauthgamer
    Stereoscopic families of permutations, and their applications. [Citation Graph (0, 0)][DBLP]
    ISTCS, 1997, pp:85-95 [Conf]
  12. Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, Éva Tardos
    Approximate classification via earthmover metrics. [Citation Graph (0, 0)][DBLP]
    SODA, 2004, pp:1079-1087 [Conf]
  13. Andrei Z. Broder, Robert Krauthgamer, Michael Mitzenmacher
    Improved classification via connectivity information. [Citation Graph (0, 0)][DBLP]
    SODA, 2000, pp:576-585 [Conf]
  14. Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang
    Integrality ratio for group Steiner trees and directed steiner trees. [Citation Graph (0, 0)][DBLP]
    SODA, 2003, pp:275-284 [Conf]
  15. Robert Krauthgamer, James R. Lee
    Navigating nets: simple algorithms for proximity search. [Citation Graph (0, 0)][DBLP]
    SODA, 2004, pp:798-807 [Conf]
  16. Robert Krauthgamer, Yuval Rabani
    Improved lower bounds for embeddings into L1. [Citation Graph (0, 0)][DBLP]
    SODA, 2006, pp:1010-1017 [Conf]
  17. Guy Kortsarz, Robert Krauthgamer
    On approximating the achromatic number. [Citation Graph (0, 0)][DBLP]
    SODA, 2001, pp:309-318 [Conf]
  18. Robert Krauthgamer, Ori Sasson
    Property testing of data dimensionality. [Citation Graph (0, 0)][DBLP]
    SODA, 2003, pp:18-27 [Conf]
  19. Kirsten Hildrum, Robert Krauthgamer, John Kubiatowicz
    Object location in realistic networks. [Citation Graph (0, 0)][DBLP]
    SPAA, 2004, pp:25-35 [Conf]
  20. Eyal Amir, Robert Krauthgamer, Satish Rao
    Constant factor approximation of vertex-cuts in planar graphs. [Citation Graph (0, 0)][DBLP]
    STOC, 2003, pp:90-99 [Conf]
  21. Uriel Feige, Robert Krauthgamer, Kobbi Nissim
    Approximating the minimum bisection size (extended abstract). [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:530-536 [Conf]
  22. Shai Halevi, Robert Krauthgamer, Eyal Kushilevitz, Kobbi Nissim
    Private approximation of NP-hard functions. [Citation Graph (0, 0)][DBLP]
    STOC, 2001, pp:550-559 [Conf]
  23. Eran Halperin, Robert Krauthgamer
    Polylogarithmic inapproximability. [Citation Graph (0, 0)][DBLP]
    STOC, 2003, pp:585-594 [Conf]
  24. T. S. Jayram, Tracy Kimbrel, Robert Krauthgamer, Baruch Schieber, Maxim Sviridenko
    Online server allocation in a server farm via benefit task systems. [Citation Graph (0, 0)][DBLP]
    STOC, 2001, pp:540-549 [Conf]
  25. Robert Krauthgamer, James R. Lee
    The intrinsic dimensionality of graphs. [Citation Graph (0, 0)][DBLP]
    STOC, 2003, pp:438-447 [Conf]
  26. Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, D. Sivakumar
    On the Hardness of Approximating Multicut and Sparsest-Cut. [Citation Graph (0, 0)][DBLP]
    Computational Complexity, 2006, v:15, n:2, pp:94-114 [Journal]
  27. Uriel Feige, Robert Krauthgamer, Kobbi Nissim
    On Cutting a Few Vertices from a Graph. [Citation Graph (0, 0)][DBLP]
    Discrete Applied Mathematics, 2003, v:127, n:3, pp:643-649 [Journal]
  28. Uriel Feige, Robert Krauthgamer
    Networks on Which Hot-Potato Routing Does Not Livelock. [Citation Graph (0, 0)][DBLP]
    Distributed Computing, 2000, v:13, n:1, pp:53-58 [Journal]
  29. Robert Krauthgamer, Nathan Linial, Avner Magen
    Metric Embeddings--Beyond One-Dimensional Distortion. [Citation Graph (0, 0)][DBLP]
    Discrete & Computational Geometry, 2004, v:31, n:3, pp:339-356 [Journal]
  30. Eran Halperin, Guy Kortsarz, Robert Krauthgamer
    Tight lower bounds for the asymmetric k-center problem [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2003, v:10, n:035, pp:- [Journal]
  31. Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Robert Krauthgamer, Joseph Naor
    Asymmetric k-center is log* n-hard to approximate. [Citation Graph (0, 0)][DBLP]
    J. ACM, 2005, v:52, n:4, pp:538-551 [Journal]
  32. Uriel Feige, Robert Krauthgamer
    Finding and certifying a large hidden clique in a semirandom graph. [Citation Graph (0, 0)][DBLP]
    Random Struct. Algorithms, 2000, v:16, n:2, pp:195-208 [Journal]
  33. Uriel Feige, Robert Krauthgamer
    A Polylogarithmic Approximation of the Minimum Bisection. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 2002, v:31, n:4, pp:1090-1118 [Journal]
  34. Uriel Feige, Robert Krauthgamer
    The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 2003, v:32, n:2, pp:345-370 [Journal]
  35. Guy Kortsarz, Robert Krauthgamer, James R. Lee
    Hardness of Approximation for Vertex-Connectivity Network Design Problems. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 2004, v:33, n:3, pp:704-720 [Journal]
  36. Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang
    Integrality Ratio for Group Steiner Trees and Directed Steiner Trees. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 2007, v:36, n:5, pp:1494-1511 [Journal]
  37. Guy Kortsarz, Robert Krauthgamer
    On Approximating the Achromatic Number. [Citation Graph (0, 0)][DBLP]
    SIAM J. Discrete Math., 2001, v:14, n:3, pp:408-422 [Journal]
  38. Robert Krauthgamer, James R. Lee
    The black-box complexity of nearest-neighbor search. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 2005, v:348, n:2-3, pp:262-276 [Journal]
  39. Parikshit Gopalan, T. S. Jayram, Robert Krauthgamer, Ravi Kumar
    Estimating the sortedness of a data stream. [Citation Graph (0, 0)][DBLP]
    SODA, 2007, pp:318-327 [Conf]
  40. Robert Krauthgamer
    On triangulation of simple networks. [Citation Graph (0, 0)][DBLP]
    SPAA, 2007, pp:8-15 [Conf]
  41. Robert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor
    Measured descent: A new embedding method for finite metrics [Citation Graph (0, 0)][DBLP]
    CoRR, 2004, v:0, n:, pp:- [Journal]

  42. Vertex Sparsifiers: New Results from Old Techniques. [Citation Graph (, )][DBLP]


  43. Proximity Algorithms for Nearly-Doubling Spaces. [Citation Graph (, )][DBLP]


  44. Approximating Sparsest Cut in Graphs of Bounded Treewidth. [Citation Graph (, )][DBLP]


  45. The Computational Hardness of Estimating Edit Distance [Extended Abstract]. [Citation Graph (, )][DBLP]


  46. The Smoothed Complexity of Edit Distance. [Citation Graph (, )][DBLP]


  47. Greedy List Intersection. [Citation Graph (, )][DBLP]


  48. Earth mover distance over high-dimensional spaces. [Citation Graph (, )][DBLP]


  49. Metric clustering via consistent labeling. [Citation Graph (, )][DBLP]


  50. Approximate line nearest neighbor in high dimensions. [Citation Graph (, )][DBLP]


  51. Overcoming the l1 non-embeddability barrier: algorithms for product metrics. [Citation Graph (, )][DBLP]


  52. How hard is it to approximate the best Nash equilibrium? [Citation Graph (, )][DBLP]


  53. Partitioning graphs into balanced components. [Citation Graph (, )][DBLP]


  54. Pricing Commodities, or How to Sell When Buyers Have Restricted Valuations. [Citation Graph (, )][DBLP]


  55. The intrinsic dimensionality of graphs. [Citation Graph (, )][DBLP]


  56. A Nonlinear Approach to Dimension Reduction [Citation Graph (, )][DBLP]


  57. Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity [Citation Graph (, )][DBLP]


  58. Approximating Sparsest Cut in Graphs of Bounded Treewidth [Citation Graph (, )][DBLP]


  59. Vertex Sparsifiers: New Results from Old Techniques [Citation Graph (, )][DBLP]


  60. Earth Mover Distance over High-Dimensional Spaces. [Citation Graph (, )][DBLP]


Search in 0.036secs, Finished in 0.039secs
NOTICE1
System may not be available sometimes or not working properly, since it is still in development with continuous upgrades
NOTICE2
The rankings that are presented on this page should NOT be considered as formal since the citation info is incomplete in DBLP
 
System created by asidirop@csd.auth.gr [http://users.auth.gr/~asidirop/] © 2002
for Data Engineering Laboratory, Department of Informatics, Aristotle University © 2002