×

zbMATH — the first resource for mathematics

Krauthgamer, Robert

Compute Distance To:
Author ID: krauthgamer.robert Recent zbMATH articles by "Krauthgamer, Robert"
Published as: Krauthgamer, R.; Krauthgamer, Robert
External Links: MGP
Documents Indexed: 96 Publications since 2000, including 1 Book
all top 5

Co-Authors

1 single-authored
12 Andoni, Alexandr
11 Gottlieb, Lee-Ad J.
9 Feige, Uriel
9 Lee, James R.
7 Kortsarz, Guy
5 Naor, Joseph Seffi
4 Halperin, Eran
4 Kamma, Lior
4 Kontorovich, Leonid Aryeh
4 Schwartz, Roy
4 Talwar, Kunal
3 Dinitz, Michael H.
3 Gupta, Anupam
3 Indyk, Piotr
3 Jayram, T. S.
3 Kumar, Ravi Shankar
3 Nissim, Kobbi
3 Rabani, Yuval
3 Trabelsi, Ohad
2 Bansal, Nikhil
2 Bartal, Yair
2 Englert, Matthias
2 Filtser, Arnold
2 Hazan, Elad
2 Kopelowitz, Tsvi
2 Makarychev, Konstantin S.
2 Mehta, Aranyak
2 Nagarajan, Viswanath
2 Nguyen, Huy L.
2 Nguyen, Huy Le
2 Onak, Krzysztof
2 Racke, Harald
2 Razenshteyn, Ilya P.
2 Rika, Havana (Inbal)
2 Roughgarden, Tim
2 Rudra, Atri
2 Srinivasan, Aravind
2 Talgam-Cohen, Inbal
2 Wagner, Tal
2 Wang, Nan
2 Zondiner, Tamar
1 Abboud, Amir
1 Abraham, Ittai
1 Amir, Amihood
1 Amir, Eyal
1 Archer, Aaron F.
1 Bar-Yossef, Ziv
1 Błasiok, Jarosław
1 Braverman, Vladimir
1 Broder, Andrei Z.
1 Charikar, Moses S.
1 Chawla, Shuchi
1 Chechik, Shiri
1 Chen, Jiecao
1 Chestnut, Stephen R.
1 Chitnis, Rajesh Hemant
1 Chlamtac, Eden
1 Chuzhoy, Julia
1 David, Roee
1 Fakcharoenphol, Jittat
1 Ficler, Jessica
1 Goldenberg, Elazar
1 Gopalan, Parikshit
1 Guha, Sudipto
1 Halevi, Shai
1 Harrelson, Chris
1 Khanna, Sanjeev
1 Kimbrel, Tracy
1 Kogan, Dmitriĭ Izrailovich
1 Kushilevitz, Eyal
1 Linial, Nathan
1 Magen, Avner
1 Mendel, Manor
1 Mitzenmacher, Michael
1 Nadler, Boaz
1 Naor, Assaf
1 Porat, Ely
1 Qin, Bo
1 Raghavendra, Prasad
1 Rao, Satish B.
1 Rika, Inbal
1 Roditty, Liam
1 Sar Shalom, Oren
1 Sasson, Ori
1 Schieber, Baruch
1 Sivakumar, Duraisamy
1 Solomon, Shay
1 Sviridenko, Maxim I.
1 Tardos, Éva
1 Vilenchik, Dan
1 Wieder, Udi
1 Woodruff, David P.
1 Yang, Lin Forrest
1 Zhang, Qin

Publications by Year

Citations contained in zbMATH

74 Publications have been cited 499 times in 371 Documents Cited by Year
On the hardness of approximating Multicut and Sparsest-Cut. Zbl 1132.68418
Chawla, Shuchi; Krauthgamer, Robert; Kumar, Ravi; Rabani, Yuval; Sivakumar, D.
38
2006
Polylogarithmic inapproximability. Zbl 1192.68321
Halperin, Eran; Krauthgamer, Robert
38
2003
Navigating nets: simple algorithms for proximity search. Zbl 1318.68071
Krauthgamer, Robert; Lee, James R.
34
2004
Measured descent: A new embedding method for finite metrics. Zbl 1108.46010
Krauthgamer, R.; Lee, James R.; Mendel, Manor; Naor, Assaf
31
2005
Finding and certifying a large hidden clique in a semirandom graph. Zbl 0940.05050
Feige, Uriel; Krauthgamer, Robert
21
2000
Hardness of approximation for vertex-connectivity network design problems. Zbl 1101.68985
Kortsarz, Guy; Krauthgamer, Robert; Lee, James R.
20
2004
A polylogarithmic approximation of the minimum bisection. Zbl 1015.68240
Feige, Uriel; Krauthgamer, Robert
19
2002
How hard is it to approximate the best Nash equilibrium? Zbl 1229.91092
Hazan, Elad; Krauthgamer, Robert
18
2011
The probable value of the Lovász–Schrijver relaxations for maximum independent set. Zbl 1021.05073
Feige, Uriel; Krauthgamer, Robert
12
2003
Fault-tolerant spanners, better and simpler. Zbl 1321.68103
Dinitz, Michael; Krauthgamer, Robert
11
2011
Preserving terminal distances using minors. Zbl 1293.05083
Krauthgamer, Robert; Nguyen, Huy L.; Zondiner, Tamar
9
2014
A polylogarithmic approximation of the minimum bisection. Zbl 1088.05068
Feige, Uriel; Krauthgamer, Robert
9
2006
Cutting corners cheaply, or how to remove Steiner points. Zbl 1328.05059
Kamma, Lior; Krauthgamer, Robert; Nguyen, Huy L.
8
2015
Vertex sparsifiers: new results from old techniques. Zbl 1302.90234
Englert, Matthias; Gupta, Anupam; Krauthgamer, Robert; Räcke, Harald; Talgam-Cohen, Inbal; Talwar, Kunal
8
2014
Polylogarithmic approximation for edit distance and the asymmetric query complexity. Zbl 1309.68228
Andoni, Alexandr; Krauthgamer, Robert; Onak, Krzysztof
8
2010
Improved lower bounds for embeddings into \(L_1\). Zbl 1191.68869
Krauthgamer, Robert; Rabani, Yuval
8
2009
Earth mover distance over high-dimensional spaces. Zbl 1192.68725
Andoni, Alexandr; Indyk, Piotr; Krauthgamer, Robert
8
2008
Improved lower bounds for embeddings into \(L_1\). Zbl 1192.90178
Krauthgamer, Robert; Rabani, Yuval
7
2006
Asymmetric \(k\)-center is \(\log^\ast n\)-hard to approximate. Zbl 1323.68297
Chuzhoy, Julia; Guha, Sudipto; Halperin, Eran; Khanna, Sanjeev; Kortsarz, Guy; Krauthgamer, Robert; Naor, Joseph
7
2005
Sketching cuts in graphs and hypergraphs. Zbl 1365.68469
Kogan, Dmitry; Krauthgamer, Robert
6
2015
Sketching and embedding are equivalent for norms. Zbl 1321.68428
Andoni, Alexandr; Krauthgamer, Robert; Razenshteyn, Ilya
6
2015
Do semidefinite relaxations solve sparse PCA up to the information limit? Zbl 1320.62138
Krauthgamer, Robert; Nadler, Boaz; Vilenchik, Dan
6
2015
Efficient classification for metric data. Zbl 1360.62332
Gottlieb, Lee-Ad; Kontorovich, Aryeh; Krauthgamer, Robert
6
2014
A nonlinear approach to dimension reduction. Zbl 1376.68150
Gottlieb, Lee-Ad; Krauthgamer, Robert
6
2011
The computational hardness of estimating edit distance. Zbl 1213.68305
Andoni, Alexandr; Krauthgamer, Robert
6
2010
Integrality ratio for group Steiner trees and directed Steiner trees. Zbl 1124.05027
Halperin, Eran; Kortsarz, Guy; Krauthgamer, Robert; Srinivasan, Aravind; Wang, Nan
6
2007
Approximate classification via earthmover metrics. Zbl 1318.68193
Archer, Aaron; Fakcharoenphol, Jittat; Harrelson, Chris; Krauthgamer, Robert; Talwar, Kunal; Tardos, Éva
6
2004
Property testing of data dimensionality. Zbl 1092.68573
Krauthgamer, Robert; Sasson, Ori
6
2003
Orienting fully dynamic graphs with worst-case time bounds. Zbl 1411.68084
Kopelowitz, Tsvi; Krauthgamer, Robert; Porat, Ely; Solomon, Shay
5
2014
Mimicking networks and succinct representations of terminal cuts. Zbl 1423.68352
Krauthgamer, Robert; Rika, Inbal
5
2013
The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. Zbl 1286.68177
Bartal, Yair; Gottlieb, Lee-Ad; Krauthgamer, Robert
5
2012
Directed spanners via flow-based linear programs. Zbl 1288.68262
Dinitz, Michael; Krauthgamer, Robert
5
2011
Vertex sparsifiers: new results from old techniques. Zbl 1302.90233
Englert, Matthias; Gupta, Anupam; Krauthgamer, Robert; Räcke, Harald; Talgam-Cohen, Inbal; Talwar, Kunal
5
2010
Approximating sparsest cut in graphs of bounded treewidth. Zbl 1304.68213
Chlamtac, Eden; Krauthgamer, Robert; Raghavendra, Prasad
5
2010
Estimating the sortedness of a data stream. Zbl 1302.68125
Gopalan, Parikshit; Jayram, T. S.; Krauthgamer, Robert; Kumar, Ravi
5
2007
On cutting a few vertices from a graph. Zbl 1019.68137
Feige, Uriel; Krauthgamer, Robert; Nissim, Kobbi
5
2003
Approximating the minimum bisection size (extended abstract). Zbl 1296.05162
Feige, Uriel; Krauthgamer, Robert; Nissim, Kobbi
5
2000
Towards \((1 + \varepsilon)\)-approximate flow sparsifiers. Zbl 1422.68280
Andoni, Alexandr; Gupta, Anupam; Krauthgamer, Robert
4
2014
Min-max graph partitioning and small set expansion. Zbl 1292.05126
Bansal, Nikhil; Feige, Uriel; Krauthgamer, Robert; Makarychev, Konstantin; Nagarajan, Viswanath; Naor, Joseph; Schwartz, Roy
4
2011
Streaming algorithms via precision sampling. Zbl 1292.68186
Andoni, Alexandr; Krauthgamer, Robert; Onak, Krzysztof
4
2011
Partitioning graphs into balanced components. Zbl 1411.68085
Krauthgamer, Robert; Naor, Joseph (Seffi); Schwartz, Roy
4
2009
The black-box complexity of nearest-neighbor search. Zbl 1081.68013
Krauthgamer, Robert; Lee, James R.
4
2005
The sketching complexity of pattern matching. Zbl 1105.68460
Bar-Yossef, Ziv; Jayram, T. S.; Krauthgamer, Robert; Kumar, Ravi
4
2004
On approximating the achromatic number. Zbl 0977.68063
Kortsarz, Guy; Krauthgamer, Robert
4
2001
On sketching quadratic forms. Zbl 1334.68091
Andoni, Alexandr; Chen, Jiecao; Krauthgamer, Robert; Qin, Bo; Woodruff, David P.; Zhang, Qin
3
2016
Approximate nearest neighbor search in metrics of planar graphs. Zbl 1375.68043
Abraham, Ittai; Chechik, Shiri; Krauthgamer, Robert; Wieder, Udi
3
2015
A nonlinear approach to dimension reduction. Zbl 1334.68249
Gottlieb, Lee-Ad; Krauthgamer, Robert
3
2015
Min-max graph partitioning and small set expansion. Zbl 1360.68639
Bansal, Nikhil; Feige, Uriel; Krauthgamer, Robert; Makarychev, Konstantin; Nagarajan, Viswanath; Naor, Joseph (Seffi); Schwartz, Roy
3
2014
Proximity algorithms for nearly doubling spaces. Zbl 1310.68240
Gottlieb, Lee-Ad; Krauthgamer, Robert
3
2013
Preserving terminal distances using minors. Zbl 1271.05092
Krauthgamer, Robert; Zondiner, Tamar
3
2012
Overcoming the \(\ell_1\) non-embeddability barrier: algorithms for product metrics. Zbl 1422.68281
Andoni, Alexandr; Indyk, Piotr; Krauthgamer, Robert
3
2009
Embedding the Ulam metric into \(\ell_{1}\). Zbl 1213.68226
Charikar, Moses; Krauthgamer, Robert
3
2006
Metric embeddings – beyond one-dimensional distortion. Zbl 1095.68086
Krauthgamer, Robert; Linial, Nathan; Magen, Avner
3
2004
Constant factor approximation of vertex-cuts in planar graphs. Zbl 1192.68867
Amir, Eyal; Krauthgamer, Robert; Rao, Satish
3
2003
Integrality ratio for group Steiner trees and directed Steiner trees. Zbl 1094.68611
Halperin, Eran; Kortsarz, Guy; Krauthgamer, Robert; Srinivasan, Aravind; Wang, Nan
3
2003
The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. Zbl 1350.68288
Bartal, Yair; Gottlieb, Lee-Ad; Krauthgamer, Robert
2
2016
The smoothed complexity of edit distance. Zbl 1295.68206
Andoni, Alexandr; Krauthgamer, Robert
2
2012
Pricing commodities. Zbl 1237.91117
Krauthgamer, Robert; Mehta, Aranyak; Rudra, Atri
2
2011
The smoothed complexity of edit distance. Zbl 1153.68563
Andoni, Alexandr; Krauthgamer, Robert
2
2008
The black-box complexity of nearest neighbor search. Zbl 1099.68604
Krauthgamer, Robert; Lee, James R.
2
2004
Private approximation of NP-hard functions. Zbl 1323.68569
Halevi, Shai; Krauthgamer, Robert; Kushilevitz, Eyal; Nissim, Kobbi
2
2001
Flow-cut gaps and face covers in planar graphs. Zbl 1434.05124
Krauthgamer, Robert; Lee, James R.; Rika, Havana (Inbal)
1
2019
Efficient regression in metric spaces via approximate Lipschitz extension. Zbl 1372.94363
Gottlieb, Lee-Ad; Kontorovich, Aryeh; Krauthgamer, Robert
1
2017
Streaming symmetric norms via measure concentration. Zbl 1369.68205
Błasiok, Jarosław; Braverman, Vladimir; Chestnut, Stephen R.; Krauthgamer, Robert; Yang, Lin F.
1
2017
Sparsification of two-variable valued constraint satisfaction problems. Zbl 1371.68112
Filtser, Arnold; Krauthgamer, Robert
1
2017
Tight bounds for Gomory-Hu-like cut counting. Zbl 1417.05090
Chitnis, Rajesh; Kamma, Lior; Krauthgamer, Robert
1
2016
Adaptive metric dimensionality reduction. Zbl 1335.68202
Gottlieb, Lee-Ad; Kontorovich, Aryeh; Krauthgamer, Robert
1
2016
Proceedings of the 27th annual ACM-SIAM symposium on discrete algorithms, SODA 2016, Arlington, VA, USA, January 10–12, 2016. Zbl 1331.68017
Krauthgamer, Robert (ed.)
1
2016
Towards resistance sparsifiers. Zbl 1375.68091
Dinitz, Michael; Krauthgamer, Robert; Wagner, Tal
1
2015
Multiply balanced \(k\)-partitioning. Zbl 1405.68234
Amir, Amihood; Ficler, Jessica; Krauthgamer, Robert; Roditty, Liam; Sar Shalom, Oren
1
2014
Metric clustering via consistent labeling. Zbl 1231.68285
Krauthgamer, Robert; Roughgarden, Tim
1
2011
Proximity algorithms for nearly-doubling spaces. Zbl 1304.68215
Gottlieb, Lee-Ad; Krauthgamer, Robert
1
2010
Metric clustering via consistent labeling. Zbl 1192.68646
Krauthgamer, Robert; Roughgarden, Tim
1
2008
The intrinsic dimensionality of graphs. Zbl 1164.05050
Krauthgamer, Robert; Lee, James R.
1
2007
Flow-cut gaps and face covers in planar graphs. Zbl 1434.05124
Krauthgamer, Robert; Lee, James R.; Rika, Havana (Inbal)
1
2019
Efficient regression in metric spaces via approximate Lipschitz extension. Zbl 1372.94363
Gottlieb, Lee-Ad; Kontorovich, Aryeh; Krauthgamer, Robert
1
2017
Streaming symmetric norms via measure concentration. Zbl 1369.68205
Błasiok, Jarosław; Braverman, Vladimir; Chestnut, Stephen R.; Krauthgamer, Robert; Yang, Lin F.
1
2017
Sparsification of two-variable valued constraint satisfaction problems. Zbl 1371.68112
Filtser, Arnold; Krauthgamer, Robert
1
2017
On sketching quadratic forms. Zbl 1334.68091
Andoni, Alexandr; Chen, Jiecao; Krauthgamer, Robert; Qin, Bo; Woodruff, David P.; Zhang, Qin
3
2016
The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. Zbl 1350.68288
Bartal, Yair; Gottlieb, Lee-Ad; Krauthgamer, Robert
2
2016
Tight bounds for Gomory-Hu-like cut counting. Zbl 1417.05090
Chitnis, Rajesh; Kamma, Lior; Krauthgamer, Robert
1
2016
Adaptive metric dimensionality reduction. Zbl 1335.68202
Gottlieb, Lee-Ad; Kontorovich, Aryeh; Krauthgamer, Robert
1
2016
Proceedings of the 27th annual ACM-SIAM symposium on discrete algorithms, SODA 2016, Arlington, VA, USA, January 10–12, 2016. Zbl 1331.68017
Krauthgamer, Robert (ed.)
1
2016
Cutting corners cheaply, or how to remove Steiner points. Zbl 1328.05059
Kamma, Lior; Krauthgamer, Robert; Nguyen, Huy L.
8
2015
Sketching cuts in graphs and hypergraphs. Zbl 1365.68469
Kogan, Dmitry; Krauthgamer, Robert
6
2015
Sketching and embedding are equivalent for norms. Zbl 1321.68428
Andoni, Alexandr; Krauthgamer, Robert; Razenshteyn, Ilya
6
2015
Do semidefinite relaxations solve sparse PCA up to the information limit? Zbl 1320.62138
Krauthgamer, Robert; Nadler, Boaz; Vilenchik, Dan
6
2015
Approximate nearest neighbor search in metrics of planar graphs. Zbl 1375.68043
Abraham, Ittai; Chechik, Shiri; Krauthgamer, Robert; Wieder, Udi
3
2015
A nonlinear approach to dimension reduction. Zbl 1334.68249
Gottlieb, Lee-Ad; Krauthgamer, Robert
3
2015
Towards resistance sparsifiers. Zbl 1375.68091
Dinitz, Michael; Krauthgamer, Robert; Wagner, Tal
1
2015
Preserving terminal distances using minors. Zbl 1293.05083
Krauthgamer, Robert; Nguyen, Huy L.; Zondiner, Tamar
9
2014
Vertex sparsifiers: new results from old techniques. Zbl 1302.90234
Englert, Matthias; Gupta, Anupam; Krauthgamer, Robert; Räcke, Harald; Talgam-Cohen, Inbal; Talwar, Kunal
8
2014
Efficient classification for metric data. Zbl 1360.62332
Gottlieb, Lee-Ad; Kontorovich, Aryeh; Krauthgamer, Robert
6
2014
Orienting fully dynamic graphs with worst-case time bounds. Zbl 1411.68084
Kopelowitz, Tsvi; Krauthgamer, Robert; Porat, Ely; Solomon, Shay
5
2014
Towards \((1 + \varepsilon)\)-approximate flow sparsifiers. Zbl 1422.68280
Andoni, Alexandr; Gupta, Anupam; Krauthgamer, Robert
4
2014
Min-max graph partitioning and small set expansion. Zbl 1360.68639
Bansal, Nikhil; Feige, Uriel; Krauthgamer, Robert; Makarychev, Konstantin; Nagarajan, Viswanath; Naor, Joseph (Seffi); Schwartz, Roy
3
2014
Multiply balanced \(k\)-partitioning. Zbl 1405.68234
Amir, Amihood; Ficler, Jessica; Krauthgamer, Robert; Roditty, Liam; Sar Shalom, Oren
1
2014
Mimicking networks and succinct representations of terminal cuts. Zbl 1423.68352
Krauthgamer, Robert; Rika, Inbal
5
2013
Proximity algorithms for nearly doubling spaces. Zbl 1310.68240
Gottlieb, Lee-Ad; Krauthgamer, Robert
3
2013
The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. Zbl 1286.68177
Bartal, Yair; Gottlieb, Lee-Ad; Krauthgamer, Robert
5
2012
Preserving terminal distances using minors. Zbl 1271.05092
Krauthgamer, Robert; Zondiner, Tamar
3
2012
The smoothed complexity of edit distance. Zbl 1295.68206
Andoni, Alexandr; Krauthgamer, Robert
2
2012
How hard is it to approximate the best Nash equilibrium? Zbl 1229.91092
Hazan, Elad; Krauthgamer, Robert
18
2011
Fault-tolerant spanners, better and simpler. Zbl 1321.68103
Dinitz, Michael; Krauthgamer, Robert
11
2011
A nonlinear approach to dimension reduction. Zbl 1376.68150
Gottlieb, Lee-Ad; Krauthgamer, Robert
6
2011
Directed spanners via flow-based linear programs. Zbl 1288.68262
Dinitz, Michael; Krauthgamer, Robert
5
2011
Min-max graph partitioning and small set expansion. Zbl 1292.05126
Bansal, Nikhil; Feige, Uriel; Krauthgamer, Robert; Makarychev, Konstantin; Nagarajan, Viswanath; Naor, Joseph; Schwartz, Roy
4
2011
Streaming algorithms via precision sampling. Zbl 1292.68186
Andoni, Alexandr; Krauthgamer, Robert; Onak, Krzysztof
4
2011
Pricing commodities. Zbl 1237.91117
Krauthgamer, Robert; Mehta, Aranyak; Rudra, Atri
2
2011
Metric clustering via consistent labeling. Zbl 1231.68285
Krauthgamer, Robert; Roughgarden, Tim
1
2011
Polylogarithmic approximation for edit distance and the asymmetric query complexity. Zbl 1309.68228
Andoni, Alexandr; Krauthgamer, Robert; Onak, Krzysztof
8
2010
The computational hardness of estimating edit distance. Zbl 1213.68305
Andoni, Alexandr; Krauthgamer, Robert
6
2010
Vertex sparsifiers: new results from old techniques. Zbl 1302.90233
Englert, Matthias; Gupta, Anupam; Krauthgamer, Robert; Räcke, Harald; Talgam-Cohen, Inbal; Talwar, Kunal
5
2010
Approximating sparsest cut in graphs of bounded treewidth. Zbl 1304.68213
Chlamtac, Eden; Krauthgamer, Robert; Raghavendra, Prasad
5
2010
Proximity algorithms for nearly-doubling spaces. Zbl 1304.68215
Gottlieb, Lee-Ad; Krauthgamer, Robert
1
2010
Improved lower bounds for embeddings into \(L_1\). Zbl 1191.68869
Krauthgamer, Robert; Rabani, Yuval
8
2009
Partitioning graphs into balanced components. Zbl 1411.68085
Krauthgamer, Robert; Naor, Joseph (Seffi); Schwartz, Roy
4
2009
Overcoming the \(\ell_1\) non-embeddability barrier: algorithms for product metrics. Zbl 1422.68281
Andoni, Alexandr; Indyk, Piotr; Krauthgamer, Robert
3
2009
Earth mover distance over high-dimensional spaces. Zbl 1192.68725
Andoni, Alexandr; Indyk, Piotr; Krauthgamer, Robert
8
2008
The smoothed complexity of edit distance. Zbl 1153.68563
Andoni, Alexandr; Krauthgamer, Robert
2
2008
Metric clustering via consistent labeling. Zbl 1192.68646
Krauthgamer, Robert; Roughgarden, Tim
1
2008
Integrality ratio for group Steiner trees and directed Steiner trees. Zbl 1124.05027
Halperin, Eran; Kortsarz, Guy; Krauthgamer, Robert; Srinivasan, Aravind; Wang, Nan
6
2007
Estimating the sortedness of a data stream. Zbl 1302.68125
Gopalan, Parikshit; Jayram, T. S.; Krauthgamer, Robert; Kumar, Ravi
5
2007
The intrinsic dimensionality of graphs. Zbl 1164.05050
Krauthgamer, Robert; Lee, James R.
1
2007
On the hardness of approximating Multicut and Sparsest-Cut. Zbl 1132.68418
Chawla, Shuchi; Krauthgamer, Robert; Kumar, Ravi; Rabani, Yuval; Sivakumar, D.
38
2006
A polylogarithmic approximation of the minimum bisection. Zbl 1088.05068
Feige, Uriel; Krauthgamer, Robert
9
2006
Improved lower bounds for embeddings into \(L_1\). Zbl 1192.90178
Krauthgamer, Robert; Rabani, Yuval
7
2006
Embedding the Ulam metric into \(\ell_{1}\). Zbl 1213.68226
Charikar, Moses; Krauthgamer, Robert
3
2006
Measured descent: A new embedding method for finite metrics. Zbl 1108.46010
Krauthgamer, R.; Lee, James R.; Mendel, Manor; Naor, Assaf
31
2005
Asymmetric \(k\)-center is \(\log^\ast n\)-hard to approximate. Zbl 1323.68297
Chuzhoy, Julia; Guha, Sudipto; Halperin, Eran; Khanna, Sanjeev; Kortsarz, Guy; Krauthgamer, Robert; Naor, Joseph
7
2005
The black-box complexity of nearest-neighbor search. Zbl 1081.68013
Krauthgamer, Robert; Lee, James R.
4
2005
Navigating nets: simple algorithms for proximity search. Zbl 1318.68071
Krauthgamer, Robert; Lee, James R.
34
2004
Hardness of approximation for vertex-connectivity network design problems. Zbl 1101.68985
Kortsarz, Guy; Krauthgamer, Robert; Lee, James R.
20
2004
Approximate classification via earthmover metrics. Zbl 1318.68193
Archer, Aaron; Fakcharoenphol, Jittat; Harrelson, Chris; Krauthgamer, Robert; Talwar, Kunal; Tardos, Éva
6
2004
The sketching complexity of pattern matching. Zbl 1105.68460
Bar-Yossef, Ziv; Jayram, T. S.; Krauthgamer, Robert; Kumar, Ravi
4
2004
Metric embeddings – beyond one-dimensional distortion. Zbl 1095.68086
Krauthgamer, Robert; Linial, Nathan; Magen, Avner
3
2004
The black-box complexity of nearest neighbor search. Zbl 1099.68604
Krauthgamer, Robert; Lee, James R.
2
2004
Polylogarithmic inapproximability. Zbl 1192.68321
Halperin, Eran; Krauthgamer, Robert
38
2003
The probable value of the Lovász–Schrijver relaxations for maximum independent set. Zbl 1021.05073
Feige, Uriel; Krauthgamer, Robert
12
2003
Property testing of data dimensionality. Zbl 1092.68573
Krauthgamer, Robert; Sasson, Ori
6
2003
On cutting a few vertices from a graph. Zbl 1019.68137
Feige, Uriel; Krauthgamer, Robert; Nissim, Kobbi
5
2003
Constant factor approximation of vertex-cuts in planar graphs. Zbl 1192.68867
Amir, Eyal; Krauthgamer, Robert; Rao, Satish
3
2003
Integrality ratio for group Steiner trees and directed Steiner trees. Zbl 1094.68611
Halperin, Eran; Kortsarz, Guy; Krauthgamer, Robert; Srinivasan, Aravind; Wang, Nan
3
2003
A polylogarithmic approximation of the minimum bisection. Zbl 1015.68240
Feige, Uriel; Krauthgamer, Robert
19
2002
On approximating the achromatic number. Zbl 0977.68063
Kortsarz, Guy; Krauthgamer, Robert
4
2001
Private approximation of NP-hard functions. Zbl 1323.68569
Halevi, Shai; Krauthgamer, Robert; Kushilevitz, Eyal; Nissim, Kobbi
2
2001
Finding and certifying a large hidden clique in a semirandom graph. Zbl 0940.05050
Feige, Uriel; Krauthgamer, Robert
21
2000
Approximating the minimum bisection size (extended abstract). Zbl 1296.05162
Feige, Uriel; Krauthgamer, Robert; Nissim, Kobbi
5
2000
all top 5

Cited by 655 Authors

13 Krauthgamer, Robert
13 Naor, Assaf
11 Lee, James R.
9 Kortsarz, Guy
9 Nutov, Zeev
8 Neiman, Ofer
6 Bentz, Cédric
6 Feige, Uriel
5 Abraham, Ittai
5 Bartal, Yair
5 Hajiaghayi, Mohammad Taghi
5 Khandekar, Rohit
5 Rauch Henzinger, Monika
5 Segev, Danny
4 Chekuri, Chandra S.
4 DasGupta, Bhaskar
4 Feldmann, Andreas Emil
4 Goranci, Gramoz
4 Gottlieb, Lee-Ad J.
4 Khot, Subhash Ajit
4 Könemann, Jochen
4 Kontorovich, Leonid Aryeh
4 Mathieu, Claire
4 Mendel, Manor
4 Peng, Pan
4 Peres, Yuval
4 Talwar, Kunal
4 Woodruff, David P.
3 Ames, Brendan P. W.
3 Andoni, Alexandr
3 Arora, Sanjeev
3 Bačkurs, Artūrs
3 Berger-Wolf, Tanya Y.
3 Bernstein, Aaron
3 Bonsma, Paul S.
3 Braun, Gábor
3 Calinescu, Gruia
3 Chakrabarti, Amit
3 Chakrabarty, Deeparnab
3 Chan, T.-H. Hubert
3 Chaovalitwongse, Wanpracha Art
3 Chlamtac, Eden
3 Chuzhoy, Julia
3 Cole, Sam
3 Deligkas, Argyrios
3 Elkin, Michael
3 Fearnley, John
3 Filtser, Arnold
3 Fung, Wai Shing
3 Gavoille, Cyril
3 Grandoni, Fabrizio
3 Gupta, Anupam
3 Kamma, Lior
3 Laekhanukit, Bundit
3 Landau, Gad M.
3 Leucci, Stefano
3 Makarychev, Konstantin S.
3 Makarychev, Yury S.
3 Newman, Ilan I.
3 Nguyen, Huy L.
3 Peleg, David
3 Pilipczuk, Marcin
3 Pokutta, Sebastian
3 Proietti, Guido
3 Rachkovskii, D. A.
3 Roditty, Liam
3 Saurabh, Saket
3 Watel, Dimitri
3 Weisser, Marc-Antoine
2 Abboud, Amir
2 Amir, Eyal
2 Ashley, Mary V.
2 Avidor, Adi
2 Barenboim, Leonid
2 Barth, Dominique
2 Baswana, Surender
2 Bateni, MohammadHossein
2 Berglin, Edvin
2 Berman, Piotr
2 Berthet, Quentin
2 Bilò, Davide
2 Biniaz, Ahmad
2 Bredereck, Robert
2 Bringmann, Karl
2 Brody, Joshua E.
2 Broersma, Hajo J.
2 Busch, Costas
2 Chandrasekaran, Venkat
2 Charikar, Moses S.
2 Chechik, Shiri
2 Chen, Jiehua
2 Cheriyan, Joseph
2 Chitnis, Rajesh Hemant
2 Choudhary, Keerti
2 Coja-Oghlan, Amin
2 Díaz, Josep
2 Dinitz, Michael H.
2 Do Ba, Khanh
2 Elbassioni, Khaled M.
2 Feldman, Vitaly
...and 555 more Authors
all top 5

Cited in 92 Serials

43 Algorithmica
34 Theoretical Computer Science
27 SIAM Journal on Computing
16 Journal of Computer and System Sciences
14 Journal of Combinatorial Optimization
11 Discrete Applied Mathematics
9 Information Processing Letters
9 The Annals of Statistics
9 SIAM Journal on Discrete Mathematics
9 Mathematical Programming. Series A. Series B
8 Theory of Computing Systems
7 Discrete & Computational Geometry
7 Journal of Discrete Algorithms
5 Combinatorica
5 Information and Computation
4 Computational Geometry
4 Distributed Computing
4 Cybernetics and Systems Analysis
4 Journal of Machine Learning Research (JMLR)
3 Israel Journal of Mathematics
3 Geometric and Functional Analysis. GAFA
3 Linear Algebra and its Applications
3 Computational Complexity
2 Journal of Graph Theory
2 Networks
2 Journal of Global Optimization
2 Bulletin of the American Mathematical Society. New Series
2 SIAM Journal on Optimization
2 Combinatorics, Probability and Computing
2 Annals of Mathematics. Second Series
2 Algorithms
2 Computer Science Review
1 Artificial Intelligence
1 Archive for Rational Mechanics and Analysis
1 Discrete Mathematics
1 Inverse Problems
1 Journal of Statistical Physics
1 Nonlinearity
1 Acta Mathematica
1 Advances in Mathematics
1 Canadian Journal of Mathematics
1 Duke Mathematical Journal
1 Information Sciences
1 Journal of Optimization Theory and Applications
1 Mathematische Annalen
1 Mathematics of Operations Research
1 Operations Research
1 Topology and its Applications
1 European Journal of Combinatorics
1 Operations Research Letters
1 Optimization
1 Probability Theory and Related Fields
1 Revista Matemática Iberoamericana
1 Computers & Operations Research
1 Journal of the American Mathematical Society
1 Mathematical and Computer Modelling
1 SIAM Journal on Matrix Analysis and Applications
1 Journal of Cryptology
1 Neural Networks
1 Random Structures & Algorithms
1 The Journal of Geometric Analysis
1 Games and Economic Behavior
1 Historia Mathematica
1 Proceedings of the National Academy of Sciences of the United States of America
1 Stochastic Processes and their Applications
1 Formal Methods in System Design
1 Journal of Computer and Systems Sciences International
1 SIAM Journal on Scientific Computing
1 Applied and Computational Harmonic Analysis
1 Economic Theory
1 Advances in Computational Mathematics
1 The Journal of Artificial Intelligence Research (JAIR)
1 Annals of Mathematics and Artificial Intelligence
1 Bernoulli
1 Sbornik: Mathematics
1 Journal of the ACM
1 Journal of the European Mathematical Society (JEMS)
1 Comptes Rendus. Mathématique. Académie des Sciences, Paris
1 Journal of Algebra and its Applications
1 Analysis and Applications (Singapore)
1 Discrete Optimization
1 Communications in Mathematical Analysis
1 Optimization Letters
1 Statistical Analysis and Data Mining
1 SIAM Journal on Imaging Sciences
1 Discrete Mathematics, Algorithms and Applications
1 Theory of Computing
1 Journal of Theoretical Biology
1 Frontiers of Computer Science
1 Analysis and Geometry in Metric Spaces
1 Special Matrices
1 Game Theory

Citations by Year