Travelled to:1 × Denmark
1 × Finland
1 × Greece
1 × Iceland
1 × United Kingdom
5 × USA
Collaborated with:J.R.Lee A.Andoni K.Nissim T.Zondiner M.Dinitz E.Halperin I.P.Razenshteyn Y.Bartal L.Gottlieb E.Amir S.Rao U.Feige T.Kopelowitz E.Porat S.Solomon S.Halevi E.Kushilevitz T.S.Jayram T.Kimbrel B.Schieber M.Sviridenko
Talks about:approxim (4) graph (3) dimension (2) distanc (2) complex (2) server (2) time (2) polylogarithm (1) inapproxim (1) salesman (1)
Person: Robert Krauthgamer
DBLP: Krauthgamer:Robert
Contributed to:
2015
201420122012201120082004200320012000Wrote 13 papers:
- STOC-2015-AndoniKR #sketching
- Sketching and Embedding are Equivalent for Norms (AA, RK, IPR), pp. 479–488.
- ICALP-v2-2014-KopelowitzKPS #bound #graph #worst-case
- Orienting Fully Dynamic Graphs with Worst-Case Time Bounds (TK, RK, EP, SS), pp. 532–543.
- ICALP-v1-2012-KrauthgamerZ #using
- Preserving Terminal Distances Using Minors (RK, TZ), pp. 594–605.
- STOC-2012-BartalGK #approximate #polynomial #problem
- The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme (YB, LAG, RK), pp. 663–672.
- STOC-2011-DinitzK #linear #source code
- Directed spanners via flow-based linear programs (MD, RK), pp. 323–332.
- ICALP-A-2008-AndoniK #complexity #distance #edit distance
- The Smoothed Complexity of Edit Distance (AA, RK), pp. 357–369.
- ICALP-2004-KrauthgamerL #black box #complexity #nearest neighbour
- The Black-Box Complexity of Nearest Neighbor Search (RK, JRL), pp. 858–869.
- STOC-2003-AmirKR #approximate #constant #graph
- Constant factor approximation of vertex-cuts in planar graphs (EA, RK, SR), pp. 90–99.
- STOC-2003-HalperinK
- Polylogarithmic inapproximability (EH, RK), pp. 585–594.
- STOC-2003-KrauthgamerL #graph
- The intrinsic dimensionality of graphs (RK, JRL), pp. 438–447.
- STOC-2001-HaleviKKN #approximate #np-hard
- Private approximation of NP-hard functions (SH, RK, EK, KN), pp. 550–559.
- STOC-2001-JayramKKSS #online
- Online server allocation in a server farm via benefit task systems (TSJ, TK, RK, BS, MS), pp. 540–549.
- STOC-2000-FeigeKN #approximate
- Approximating the minimum bisection size (UF, RK, KN), pp. 530–536.