×

zbMATH — the first resource for mathematics

Feige, Uriel

Compute Distance To:
Author ID: feige.uriel Recent zbMATH articles by "Feige, Uriel"
Published as: Feige, Uriel; Feige, Uri; Feige, U.
External Links: MGP · Wikidata · dblp
Documents Indexed: 163 Publications since 1988
all top 5

Co-Authors

28 single-authored
9 Kilian, Joe
9 Krauthgamer, Robert
7 Langberg, Michael
7 Reichman, Daniel
6 Hajiaghayi, Mohammad Taghi
6 Ofek, Eran
6 Tennenholtz, Moshe
5 Shamir, Adi
4 David, Roee
4 Jozeph, Shlomo
4 Mirrokni, Vahab S.
4 Naor, Joseph Seffi
4 Talgam-Cohen, Inbal
4 Vilenchik, Dan
3 Aumann, Yonatan
3 Azar, Yossi
3 Feldman, Michal
3 Kogan, Shimon
3 Kortsarz, Guy
3 Krivelevich, Michael
3 Lee, James R.
3 Lovász, László
3 Mossel, Elchanan
3 Naor, Moni
3 Nissim, Kobbi
3 Peleg, David
3 Raghavan, Prabhakar
3 Schechtman, Gideon
3 Singh, Mohit
3 Tetali, Prasad
2 Afek, Yehuda
2 Alon, Noga M.
2 Asadpour, Arash
2 Babichenko, Yakov
2 Bansal, Nikhil
2 Bar-Ilan, Judit
2 Barnes, Greg
2 Chlamtac, Eden
2 Chrobak, Marek
2 Coja-Oghlan, Amin
2 Demaine, Erik D.
2 Gafni, Eli M.
2 Glasner, Daniel
2 Halldórsson, Magnús Mar
2 Immorlica, Nicole
2 Karpinski, Marek
2 Khanna, Sanjeev
2 Li, Fei
2 Linial, Nathan
2 Mahdian, Mohammad
2 Makarychev, Konstantin S.
2 Nagarajan, Viswanath
2 Nazerzadeh, Hamid
2 Saberi, Amin
2 Salavatipour, Mohammad R.
2 Schwartz, Roy
2 Sudakov, Benny
2 Talwar, Kunal
2 Upfal, Eli
2 Vondrák, Jan
1 Babaioff, Moshe
1 Bhaskara, Aditya
1 Bordenave, Charles
1 Broder, Andrei Z.
1 Canetti, Ran
1 Charikar, Moses S.
1 Coppersmith, Don
1 Devanur, Nikhil R.
1 Dubey, Chandan K.
1 Dwork, Cynthia
1 Fiat, Amos
1 Flaxman, Abraham D.
1 Frieze, Alan Michael
1 Gamarnik, David
1 Gamzu, Iftah
1 Goldreich, Oded
1 Goldwasser, Shafi
1 Hermon, Jonathan
1 Hitron, Yael
1 Izsak, Rani
1 Kenyon, Anne
1 Killian, Joe
1 Koren, Tomer
1 Kulkarni, Janardhan
1 Lapidot, Dror
1 Li, Shi
1 Lund, Carsten
1 Mansour, Yishay
1 Micciancio, Daniele
1 Moscibroda, Thomas
1 Neeman, Joe
1 Patt-Shamir, Boaz
1 Rabinovich, Yuri
1 Rácz, Miklós Z.
1 Raghavendra, Prasad
1 Ravi, Ramamoorthi
1 Rayzman, Giora
1 Ron, Dorit
1 Safra, Muli
1 Safra, Shmuel
...and 13 more Co-Authors

Publications by Year

Citations contained in zbMATH Open

129 Publications have been cited 2,166 times in 1,789 Documents Cited by Year
A threshold of \(\ln n\) for approximating set cover. Zbl 1065.68573
Feige, Uriel
402
1998
The dense \(k\)-subgraph problem. Zbl 0969.68117
Feige, U.; Kortsarz, G.; Peleg, D.
94
2001
Zero knowledge and the chromatic number. Zbl 0921.68089
Feige, Uriel; Kilian, Joe
76
1998
Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph. Zbl 1293.05200
Bhaskara, Aditya; Charikar, Moses; Chlamtac, Eden; Feige, Uriel; Vijayaraghavan, Aravindan
63
2010
Zero-knowledge proofs of identity. Zbl 0659.94006
Feige, Uriel; Fiat, Amos; Shamir, Adi
63
1988
A threshold of \(\ln n\) for approximating set cover. Zbl 0922.68067
Feige, Uriel
62
1996
Maximizing non-monotone submodular functions. Zbl 1230.90198
Feige, Uriel; Mirrokni, Vahab S.; Vondrák, Jan
61
2011
Interactive proofs and the hardness of approximating cliques. Zbl 0882.68129
Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario
59
1996
Randomized broadcast in networks. Zbl 0712.68011
Feige, Uriel; Peleg, David; Raghavan, Prabhakar; Upfal, Eli
56
1990
Improved approximation algorithms for minimum weight vertex separators. Zbl 1172.68063
Feige, Uriel; Hajiaghayi, MohammadTaghi; Lee, James R.
55
2009
Spectral techniques applied to sparse random graphs. Zbl 1076.05073
Feige, Uriel; Ofek, Eran
47
2005
Relations between average case complexity and approximation complexity. Zbl 1192.68358
Feige, Uriel
45
2002
Adaptively secure multi-party computation. Zbl 0922.68048
Canetti, Ran; Feige, Uri; Goldreich, Oded; Naor, Moni
42
1996
Approximation algorithms for maximization problems arising in graph partitioning. Zbl 1017.68086
Feige, Uriel; Langberg, Michael
40
2001
A tight upper bound on the cover time for random walks on graphs. Zbl 0811.60060
Feige, Uriel
37
1995
Multiple noninteractive zero knowledge proofs under general assumptions. Zbl 1018.94015
Feige, Uriel; Lapidot, Dror; Shamir, Adi
36
1999
A tight lower bound on the cover time for random walks on graphs. Zbl 0832.60016
Feige, Uriel
36
1995
Computing with noisy information. Zbl 0813.68057
Feige, Uriel; Raghavan, Prabhakar; Peleg, David; Upfal, Eli
32
1994
Approximating min sum set cover. Zbl 1082.68126
Feige, Uriel; Lovász, László; Tetali, Prasad
28
2004
Approximating the domatic number. Zbl 1021.05072
Feige, Uriel; Halldórsson, Magnús M.; Kortsarz, Guy; Srinivasan, Aravind
28
2002
Derandomized graph products. Zbl 0816.60070
Alon, Noga; Feige, Uriel; Wigderson, Avi; Zuckerman, David
28
1995
Zero knowledge proofs of knowledge in two rounds. Zbl 0722.68045
Feige, U.; Shamir, A.
28
1990
On maximizing welfare when utility functions are subadditive. Zbl 1185.68855
Feige, Uriel
27
2009
Robust combinatorial optimization with exponential scenarios. Zbl 1136.90451
Feige, Uriel; Jain, Kamal; Mahdian, Mohammad; Mirrokni, Vahab
25
2007
A minimal model for secure computation (extended abstract). Zbl 1344.68030
Feige, Uri; Killian, Joe; Naor, Moni
25
1994
Approximating the bandwidth via volume respecting embeddings. Zbl 0958.68191
Feige, Uriel
24
2000
Approximating maximum clique by removing subgraphs. Zbl 1068.05052
Feige, Uriel
23
2004
Finding and certifying a large hidden clique in a semirandom graph. Zbl 0940.05050
Feige, Uriel; Krauthgamer, Robert
22
2000
On sums of independent random variables with unbounded variance and estimating the average degree in a graph. Zbl 1098.60026
Feige, Uriel
20
2006
Combination can be hard: Approximability of the unique coverage problem. Zbl 1192.68353
Demaine, Erik D.; Feige, Uriel; Hajiaghayi, Mohammadtaghi; Salavatipour, Mohammad R.
20
2008
On the optimality of the random hyperplane rounding technique for MAX CUT. Zbl 1005.90052
Feige, Uriel; Schechtman, Gideon
19
2002
A polylogarithmic approximation of the minimum bisection. Zbl 1015.68240
Feige, Uriel; Krauthgamer, Robert
18
2002
Improved approximation algorithms for minimum-weight vertex separators (extended abstract). Zbl 1192.68893
Feige, Uriel; Hajiaghayi, Mohammad Taghi; Lee, James R.
18
2005
Heuristics for semirandom graph problems. Zbl 1006.68103
Feige, Uriel; Kilian, Joe
17
2001
Contagious sets in expanders. Zbl 1375.05061
Coja-Oghlan, Amin; Feige, Uriel; Krivelevich, Michael; Reichman, Daniel
17
2015
On maximizing welfare when utility functions are subadditive. Zbl 1301.68270
Feige, Uriel
15
2006
The \(RPR^{2}\) rounding technique for semidefinite programs. Zbl 1113.90116
Feige, Uriel; Langberg, Michael
14
2006
Finding hidden cliques in linear time. Zbl 1355.05186
Feige, Uriel; Ron, Dorit
14
2010
Coping with the NP-hardness of the graph bandwidth problem. Zbl 0966.68513
Feige, Uriel
13
2000
Random walks on regular and irregular graphs. Zbl 0853.05075
Coppersmith, Don; Feige, Uriel; Shearer, James
12
1996
Approximating the bandwidth via volume respecting embeddings (extended abstract). Zbl 1027.68650
Feige, Uriel
12
1998
The probable value of the Lovász–Schrijver relaxations for maximum independent set. Zbl 1021.05073
Feige, Uriel; Krauthgamer, Robert
12
2003
Approximating maximum edge coloring in multigraphs. Zbl 1013.90110
Feige, Uriel; Ofek, Eran; Wieder, Udi
12
2002
Randomized graph products, chromatic numbers, and the Lovasz \(\vartheta\)-function. Zbl 1058.94517
Feige, Uriel
11
1995
An improved approximation ratio for the minimum linear arrangement problem. Zbl 1185.68856
Feige, Uriel; Lee, James R.
11
2007
Finding small balanced separators. Zbl 1301.68159
Feige, Uriel; Mahdian, Mohammad
11
2006
On allocations that maximize fairness. Zbl 1192.91083
Feige, Uriel
11
2008
Improved approximation of max-cut on graphs of bounded degree. Zbl 1050.68110
Feige, Uriel; Karpinski, Marek; Langberg, Michael
10
2002
Improved approximation ratios for traveling salesperson tours and paths in directed graphs. Zbl 1171.90507
Feige, Uriel; Singh, Mohit
10
2007
Santa Claus meets hypergraph matchings. Zbl 1295.05165
Asadpour, Arash; Feige, Uriel; Saberi, Amin
10
2012
Combination can be hard: Approximability of the unique coverage problem. Zbl 1192.68316
Demaine, Erik D.; Feige, Uriel; Hajiaghayi, Mohammad Taghi; Salavatipour, Mohammad R.
10
2006
On limited versus polynomial nondeterminism. Zbl 0924.68080
Feige, Uriel; Kilian, Joe
9
1997
Improved bounds for acyclic job shop scheduling (extended abstract). Zbl 1027.68512
Feige, Uriel; Scheideler, Christian
9
1998
A polylogarithmic approximation of the minimum bisection. Zbl 1088.05068
Feige, Uriel; Krauthgamer, Robert
9
2006
Santa Claus meets hypergraph matchings. Zbl 1159.68663
Asadpour, Arash; Feige, Uriel; Saberi, Amin
9
2008
The submodular welfare problem with demand queries. Zbl 1213.68703
Feige, Uriel; Vondrák, Jan
9
2010
Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function. Zbl 0880.05032
Feige, U.
8
1997
Contagious sets in random graphs. Zbl 1387.05233
Feige, Uriel; Krivelevich, Michael; Reichman, Daniel
8
2017
Welfare maximization and the supermodular degree. Zbl 1362.91022
Feige, Uriel; Izsak, Rani
7
2013
Exact analysis of hot-potato routing. (Extended abstract). Zbl 0977.68544
Feige, Uriel; Raghavan, Prabhakar
6
1992
On the hardness of computing the permanent of random matrices. Zbl 0956.65037
Feige, Uriel; Lund, Carsten
6
1997
Short random walks on graphs. Zbl 0843.60065
Barnes, Greg; Feige, Uriel
6
1996
The inapproximability of lattice and coding problems with preprocessing. Zbl 1106.68046
Feige, Uriel; Micciancio, Daniele
6
2004
A note on approximating Max-Bisection on regular graphs. Zbl 1032.68119
Feige, U.; Karpinski, M.; Langberg, M.
6
2001
Error reduction by parallel repetition - a negative result. Zbl 1017.68052
Feige, Uriel; Verbitsky, Oleg
6
2002
Making games short. (Extended abstract). Zbl 0983.91016
Feige, Uriel; Kilian, Joe
6
1999
Approximating the bandwidth of caterpillars. Zbl 1142.05366
Feige, Uriel; Talwar, Kunal
6
2005
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
6
2011
Approximating the domatic number. Zbl 1296.05150
Feige, Uriel; Halldórsson, Magnús M.; Kortsarz, Guy
6
2000
Approximating the minimum bisection size (extended abstract). Zbl 1296.05162
Feige, Uriel; Krauthgamer, Robert; Nissim, Kobbi
6
2000
Short random walks on graphs. Zbl 1310.05188
Barnes, Greg; Feige, Uriel
6
1993
Oblivious algorithms for the maximum directed cut problem. Zbl 1315.68279
Feige, Uriel; Jozeph, Shlomo
6
2015
Hardness results for approximating the bandwidth. Zbl 1215.68104
Dubey, Chandan; Feige, Uriel; Unger, Walter
6
2011
Impossibility results for recycling random bits in two-prover proof systems. Zbl 0968.68541
Feige, Uriel; Kilian, Joe
5
1995
Approximating the bandwidth of caterpillars. Zbl 1194.68170
Feige, Uriel; Talwar, Kunal
5
2009
Two-prover protocols—low error at affordable rates. Zbl 0959.68112
Feige, Uriel; Kilian, Joe
5
2000
The \(\text{RPR}^2\) rounding technique for semidefinite programs. Zbl 0986.90041
Feige, Uriel; Langberg, Michael
5
2001
Balanced coloring of bipartite graphs. Zbl 1205.05087
Feige, Uriel; Kogan, Shimon
5
2010
Collecting coupons on trees, and the cover time of random walks. Zbl 0897.05082
Feige, Uriel
4
1997
Easily refutable subformulas of large random 3CNF formulas. Zbl 1099.68641
Feige, Uriel; Ofek, Eran
4
2004
On cutting a few vertices from a graph. Zbl 1019.68137
Feige, Uriel; Krauthgamer, Robert; Nissim, Kobbi
4
2003
On the power of two, three and four probes. Zbl 1422.68040
Alon, Noga; Feige, Uriel
4
2009
Easily refutable subformulas of large random 3CNF formulas. Zbl 1213.68329
Feige, Uriel; Ofek, Eran
4
2007
Two prover protocols, low error at affordable rates. Zbl 1345.03106
Feige, Uri; Kilian, Joe
4
1994
A spectrum of time-space trade-offs for undirected \(s-t\) connectivity. Zbl 0878.68068
Feige, Uriel
3
1997
On systems of linear equations with two variables per equation. Zbl 1105.68047
Feige, Uriel; Reichman, Daniel
3
2004
Graphs with tiny vector chromatic numbers and huge chromatic numbers. Zbl 1105.68088
Feige, Uriel; Langberg, Michael; Schechtman, Gideon
3
2004
Low communication 2-prover zero-knowledge proofs for NP. Zbl 0925.68143
Dwork, Cynthia; Feige, Uri; Kilian, Joe; Naor, Moni; Safra, Muli
3
1993
Recoverable values for independent sets. Zbl 1307.05174
Feige, Uriel; Reichman, Daniel
3
2015
On the integrality ratio of semidefinite relaxations of MAX CUT. Zbl 1323.68298
Feige, Uriel; Schechtman, Gideon
3
2001
Complete convergence of message passing algorithms for some satisfiability problems. Zbl 1155.68507
Feige, Uriel; Mossel, Elchanan; Vilenchik, Dan
3
2006
On the complexity of finding balanced oneway cuts. Zbl 1175.68188
Feige, Uriel; Yahalom, Orly
3
2003
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
On sums of independent random variables with unbounded variance, and estimating the average degree in a graph. Zbl 1192.60021
Feige, Uriel
3
2004
Mechanism design with uncertain inputs, (to err is human, to forgive divine). Zbl 1288.91105
Feige, Uriel; Tennenholtz, Moshe
3
2011
Finding cliques using few probes. Zbl 1442.05207
Feige, Uriel; Gamarnik, David; Neeman, Joe; Rácz, Miklós Z.; Tetali, Prasad
3
2020
On the hardness of approximating \({\mathcal N}{\mathcal P}\) witnesses. Zbl 0976.90081
Feige, Uriel; Langberg, Michael; Nissim, Kobbi
2
2000
Multi-oracle interactive protocols with constant space verifiers. Zbl 0757.68050
Feige, Uriel; Shamir, Adi
2
1992
PASS approximation: a framework for analyzing and designing heuristics. Zbl 1298.90133
Feige, Uriel; Immorlica, Nicole; Mirrokni, Vahab S.; Nazerzadeh, Hamid
2
2013
Random walks with the minimum degree local rule have \(O(N^2)\) cover time. Zbl 1410.05183
David, Roee; Feige, Uriel
2
2017
Target set selection for conservative populations. Zbl 07412176
Feige, Uriel; Kogan, Shimon
1
2021
Finding cliques using few probes. Zbl 1442.05207
Feige, Uriel; Gamarnik, David; Neeman, Joe; Rácz, Miklós Z.; Tetali, Prasad
3
2020
Approximate modularity revisited. Zbl 1437.68072
Feige, Uriel; Feldman, Michal; Talgam-Cohen, Inbal
1
2020
Shotgun assembly of random jigsaw puzzles. Zbl 1450.05023
Bordenave, Charles; Feige, Uriel; Mossel, Elchanan
1
2020
A polynomial time constant approximation for minimizing total weighted flow-time. Zbl 1431.68153
Feige, Uriel; Kulkarni, Janardhan; Li, Shi
2
2019
A new approach to fair distribution of welfare. Zbl 1435.91106
Babaioff, Moshe; Feige, Uriel
1
2019
The ordered covering problem. Zbl 1459.05256
Feige, Uriel; Hitron, Yael
1
2018
Contagious sets in random graphs. Zbl 1387.05233
Feige, Uriel; Krivelevich, Michael; Reichman, Daniel
8
2017
Random walks with the minimum degree local rule have \(O(N^2)\) cover time. Zbl 1410.05183
David, Roee; Feige, Uriel
2
2017
Approximate modularity revisited. Zbl 1370.68150
Feige, Uriel; Feldman, Michal; Talgam-Cohen, Inbal
2
2017
Chasing ghosts: competing with stateful policies. Zbl 1410.91168
Feige, Uriel; Koren, Tomer; Tennenholtz, Moshe
2
2017
On giant components and treewidth in the layers model. Zbl 1338.05247
Feige, Uriel; Hermon, Jonathan; Reichman, Daniel
1
2016
On the effect of randomness on planted 3-coloring models. Zbl 1376.68052
David, Roee; Feige, Uriel
1
2016
Contagious sets in expanders. Zbl 1375.05061
Coja-Oghlan, Amin; Feige, Uriel; Krivelevich, Michael; Reichman, Daniel
17
2015
Oblivious algorithms for the maximum directed cut problem. Zbl 1315.68279
Feige, Uriel; Jozeph, Shlomo
6
2015
Recoverable values for independent sets. Zbl 1307.05174
Feige, Uriel; Reichman, Daniel
3
2015
Why are images smooth? Zbl 1366.68347
Feige, Uriel
1
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
Short tours through large linear forests. Zbl 1418.90274
Feige, Uriel; Ravi, R.; Singh, Mohit
2
2014
Demand queries with preprocessing. Zbl 1410.68418
Feige, Uriel; Jozeph, Shlomo
1
2014
Musical chairs. Zbl 1315.68265
Afek, Yehuda; Babichenko, Yakov; Feige, Uriel; Gafni, Eli; Linial, Nati; Sudakov, Benny
1
2014
Welfare maximization and the supermodular degree. Zbl 1362.91022
Feige, Uriel; Izsak, Rani
7
2013
PASS approximation: a framework for analyzing and designing heuristics. Zbl 1298.90133
Feige, Uriel; Immorlica, Nicole; Mirrokni, Vahab S.; Nazerzadeh, Hamid
2
2013
Santa Claus meets hypergraph matchings. Zbl 1295.05165
Asadpour, Arash; Feige, Uriel; Saberi, Amin
10
2012
Maximizing non-monotone submodular functions. Zbl 1230.90198
Feige, Uriel; Mirrokni, Vahab S.; Vondrák, Jan
61
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
6
2011
Hardness results for approximating the bandwidth. Zbl 1215.68104
Dubey, Chandan; Feige, Uriel; Unger, Walter
6
2011
Mechanism design with uncertain inputs, (to err is human, to forgive divine). Zbl 1288.91105
Feige, Uriel; Tennenholtz, Moshe
3
2011
Oblivious collaboration. Zbl 1350.68037
Afek, Yehuda; Babichenko, Yakov; Feige, Uriel; Gafni, Eli; Linial, Nati; Sudakov, Benny
2
2011
Buffer management for colored packets with deadlines. Zbl 1253.68067
Azar, Yossi; Feige, Uriel; Gamzu, Iftah; Moscibroda, Thomas; Raghavendra, Prasad
1
2011
Recoverable values for independent sets. Zbl 1334.68087
Feige, Uriel; Reichman, Daniel
1
2011
Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph. Zbl 1293.05200
Bhaskara, Aditya; Charikar, Moses; Chlamtac, Eden; Feige, Uriel; Vijayaraghavan, Aravindan
63
2010
Finding hidden cliques in linear time. Zbl 1355.05186
Feige, Uriel; Ron, Dorit
14
2010
The submodular welfare problem with demand queries. Zbl 1213.68703
Feige, Uriel; Vondrák, Jan
9
2010
Balanced coloring of bipartite graphs. Zbl 1205.05087
Feige, Uriel; Kogan, Shimon
5
2010
On optimal strategies for a hat game on graphs. Zbl 1223.05190
Feige, Uriel
2
2010
Responsive lotteries. Zbl 1310.91070
Feige, Uriel; Tennenholtz, Moshe
2
2010
A direct reduction from \(k\)-player to 2-player approximate Nash equilibrium. Zbl 1310.91011
Feige, Uriel; Talgam-Cohen, Inbal
1
2010
Improved approximation algorithms for minimum weight vertex separators. Zbl 1172.68063
Feige, Uriel; Hajiaghayi, MohammadTaghi; Lee, James R.
55
2009
On maximizing welfare when utility functions are subadditive. Zbl 1185.68855
Feige, Uriel
27
2009
Approximating the bandwidth of caterpillars. Zbl 1194.68170
Feige, Uriel; Talwar, Kunal
5
2009
On the power of two, three and four probes. Zbl 1422.68040
Alon, Noga; Feige, Uriel
4
2009
On smoothed \(k\)-CNF formulas and the Walksat algorithm. Zbl 1421.68059
Coja-Oghlan, Amin; Feige, Uriel; Frieze, Alan; Krivelevich, Michael; Vilenchik, Dan
2
2009
PASS approximation. A framework for analyzing and designing heuristics. Zbl 1254.68242
Feige, Uriel; Immorlica, Nicole; Mirrokni, Vahab S.; Nazerzadeh, Hamid
2
2009
Combination can be hard: Approximability of the unique coverage problem. Zbl 1192.68353
Demaine, Erik D.; Feige, Uriel; Hajiaghayi, Mohammadtaghi; Salavatipour, Mohammad R.
20
2008
On allocations that maximize fairness. Zbl 1192.91083
Feige, Uriel
11
2008
Santa Claus meets hypergraph matchings. Zbl 1159.68663
Asadpour, Arash; Feige, Uriel; Saberi, Amin
9
2008
Edge coloring and decompositions of weighted graphs. Zbl 1158.05318
Feige, Uriel; Singh, Mohit
2
2008
Finding a maximum independent set in a sparse random graph. Zbl 1167.05329
Feige, Uriel; Ofek, Eran
1
2008
Robust combinatorial optimization with exponential scenarios. Zbl 1136.90451
Feige, Uriel; Jain, Kamal; Mahdian, Mohammad; Mirrokni, Vahab
25
2007
An improved approximation ratio for the minimum linear arrangement problem. Zbl 1185.68856
Feige, Uriel; Lee, James R.
11
2007
Improved approximation ratios for traveling salesperson tours and paths in directed graphs. Zbl 1171.90507
Feige, Uriel; Singh, Mohit
10
2007
Easily refutable subformulas of large random 3CNF formulas. Zbl 1213.68329
Feige, Uriel; Ofek, Eran
4
2007
On sums of independent random variables with unbounded variance and estimating the average degree in a graph. Zbl 1098.60026
Feige, Uriel
20
2006
On maximizing welfare when utility functions are subadditive. Zbl 1301.68270
Feige, Uriel
15
2006
The \(RPR^{2}\) rounding technique for semidefinite programs. Zbl 1113.90116
Feige, Uriel; Langberg, Michael
14
2006
Finding small balanced separators. Zbl 1301.68159
Feige, Uriel; Mahdian, Mohammad
11
2006
Combination can be hard: Approximability of the unique coverage problem. Zbl 1192.68316
Demaine, Erik D.; Feige, Uriel; Hajiaghayi, Mohammad Taghi; Salavatipour, Mohammad R.
10
2006
A polylogarithmic approximation of the minimum bisection. Zbl 1088.05068
Feige, Uriel; Krauthgamer, Robert
9
2006
Complete convergence of message passing algorithms for some satisfiability problems. Zbl 1155.68507
Feige, Uriel; Mossel, Elchanan; Vilenchik, Dan
3
2006
On the hardness of approximating max-satisfy. Zbl 1185.68350
Feige, Uriel; Reichman, Daniel
2
2006
Spectral techniques applied to sparse random graphs. Zbl 1076.05073
Feige, Uriel; Ofek, Eran
47
2005
Improved approximation algorithms for minimum-weight vertex separators (extended abstract). Zbl 1192.68893
Feige, Uriel; Hajiaghayi, Mohammad Taghi; Lee, James R.
18
2005
Approximating the bandwidth of caterpillars. Zbl 1142.05366
Feige, Uriel; Talwar, Kunal
6
2005
Approximating min sum set cover. Zbl 1082.68126
Feige, Uriel; Lovász, László; Tetali, Prasad
28
2004
Approximating maximum clique by removing subgraphs. Zbl 1068.05052
Feige, Uriel
23
2004
The inapproximability of lattice and coding problems with preprocessing. Zbl 1106.68046
Feige, Uriel; Micciancio, Daniele
6
2004
Easily refutable subformulas of large random 3CNF formulas. Zbl 1099.68641
Feige, Uriel; Ofek, Eran
4
2004
On systems of linear equations with two variables per equation. Zbl 1105.68047
Feige, Uriel; Reichman, Daniel
3
2004
Graphs with tiny vector chromatic numbers and huge chromatic numbers. Zbl 1105.68088
Feige, Uriel; Langberg, Michael; Schechtman, Gideon
3
2004
On sums of independent random variables with unbounded variance, and estimating the average degree in a graph. Zbl 1192.60021
Feige, Uriel
3
2004
The probable value of the Lovász–Schrijver relaxations for maximum independent set. Zbl 1021.05073
Feige, Uriel; Krauthgamer, Robert
12
2003
On cutting a few vertices from a graph. Zbl 1019.68137
Feige, Uriel; Krauthgamer, Robert; Nissim, Kobbi
4
2003
On the complexity of finding balanced oneway cuts. Zbl 1175.68188
Feige, Uriel; Yahalom, Orly
3
2003
Deterministic approximation of the cover time. Zbl 1048.68061
Feige, Uriel; Rabinovich, Yuri
1
2003
Relations between average case complexity and approximation complexity. Zbl 1192.68358
Feige, Uriel
45
2002
Approximating the domatic number. Zbl 1021.05072
Feige, Uriel; Halldórsson, Magnús M.; Kortsarz, Guy; Srinivasan, Aravind
28
2002
On the optimality of the random hyperplane rounding technique for MAX CUT. Zbl 1005.90052
Feige, Uriel; Schechtman, Gideon
19
2002
A polylogarithmic approximation of the minimum bisection. Zbl 1015.68240
Feige, Uriel; Krauthgamer, Robert
18
2002
Approximating maximum edge coloring in multigraphs. Zbl 1013.90110
Feige, Uriel; Ofek, Eran; Wieder, Udi
12
2002
Improved approximation of max-cut on graphs of bounded degree. Zbl 1050.68110
Feige, Uriel; Karpinski, Marek; Langberg, Michael
10
2002
Error reduction by parallel repetition - a negative result. Zbl 1017.68052
Feige, Uriel; Verbitsky, Oleg
6
2002
Approximating min-sum set cover. Zbl 1013.90111
Feige, Uriel; Lovász, László; Tetali, Prasad
1
2002
The dense \(k\)-subgraph problem. Zbl 0969.68117
Feige, U.; Kortsarz, G.; Peleg, D.
94
2001
Approximation algorithms for maximization problems arising in graph partitioning. Zbl 1017.68086
Feige, Uriel; Langberg, Michael
40
2001
Heuristics for semirandom graph problems. Zbl 1006.68103
Feige, Uriel; Kilian, Joe
17
2001
A note on approximating Max-Bisection on regular graphs. Zbl 1032.68119
Feige, U.; Karpinski, M.; Langberg, M.
6
2001
The \(\text{RPR}^2\) rounding technique for semidefinite programs. Zbl 0986.90041
Feige, Uriel; Langberg, Michael
5
2001
On the integrality ratio of semidefinite relaxations of MAX CUT. Zbl 1323.68298
Feige, Uriel; Schechtman, Gideon
3
2001
Approximating the bandwidth via volume respecting embeddings. Zbl 0958.68191
Feige, Uriel
24
2000
Finding and certifying a large hidden clique in a semirandom graph. Zbl 0940.05050
Feige, Uriel; Krauthgamer, Robert
22
2000
Coping with the NP-hardness of the graph bandwidth problem. Zbl 0966.68513
Feige, Uriel
13
2000
Approximating the domatic number. Zbl 1296.05150
Feige, Uriel; Halldórsson, Magnús M.; Kortsarz, Guy
6
2000
Approximating the minimum bisection size (extended abstract). Zbl 1296.05162
Feige, Uriel; Krauthgamer, Robert; Nissim, Kobbi
6
2000
Two-prover protocols—low error at affordable rates. Zbl 0959.68112
Feige, Uriel; Kilian, Joe
5
2000
On the hardness of approximating \({\mathcal N}{\mathcal P}\) witnesses. Zbl 0976.90081
Feige, Uriel; Langberg, Michael; Nissim, Kobbi
2
2000
Finding OR in a noisy broadcast network. Zbl 1339.68016
Feige, Uriel; Kilian, Joe
1
2000
Multiple noninteractive zero knowledge proofs under general assumptions. Zbl 1018.94015
Feige, Uriel; Lapidot, Dror; Shamir, Adi
36
1999
Making games short. (Extended abstract). Zbl 0983.91016
Feige, Uriel; Kilian, Joe
6
1999
A threshold of \(\ln n\) for approximating set cover. Zbl 1065.68573
Feige, Uriel
402
1998
...and 29 more Documents
all top 5

Cited by 2,818 Authors

30 Feige, Uriel
19 Kortsarz, Guy
19 Paschos, Vangelis Th.
19 Xu, Dachuan
18 Saurabh, Saket
16 Wu, Weili
15 Sauerwald, Thomas
14 Applebaum, Benny
14 Fomin, Fedor V.
13 Gargano, Luisa
12 Du, Ding-Zhu
12 Goldreich, Oded
12 Vaccaro, Ugo
11 Caragiannis, Ioannis
11 Ishai, Yuval
10 Coja-Oghlan, Amin
10 Escoffier, Bruno
10 Hajiaghayi, Mohammad Taghi
10 Halldórsson, Magnús Mar
10 Lokshtanov, Daniel
10 Segev, Danny
10 Spirakis, Paul G.
10 Sviridenko, Maxim I.
10 Zhang, Zhao
9 Alon, Noga M.
9 Cooper, Colin
9 Cordasco, Gennaro
9 DasGupta, Bhaskar
9 Elsässer, Robert
9 Feldman, Moran
9 Fraigniaud, Pierre
9 Kaklamanis, Christos
9 Peleg, David
8 Bazgan, Cristina
8 Chekuri, Chandra S.
8 Fiorini, Samuel
8 Hazay, Carmit
8 Krumke, Sven Oliver
8 Pérennes, Stéphane
8 Pilipczuk, Marcin L.
8 Ron, Dana
8 Sudakov, Benny
8 Trevisan, Luca
8 Yung, Moti
8 Zenklusen, Rico
7 Cygan, Marek
7 Frieze, Alan Michael
7 Goyal, Vineet
7 Joret, Gwenaël
7 Khot, Subhash Ajit
7 Levin, Asaf
7 Mirrokni, Vahab S.
7 Mishra, Sounaka
7 Monaco, Gianpiero
7 Monnot, Jérôme
7 Ostrovsky, Rafail
7 Reichman, Daniel
7 Rescigno, Adele Anna
7 Roughgarden, Tim
7 Vaikuntanathan, Vinod
7 Venkitasubramaniam, Muthuramakrishnan
7 Wu, Chenchen
6 Asahiro, Yuichi
6 Avin, Chen
6 Bansal, Nikhil
6 Bellare, Mihir
6 Berenbrink, Petra
6 Bitansky, Nir
6 Bonomo-Braberman, Flavia
6 Cardinal, Jean
6 Chlamtac, Eden
6 Dobzinski, Shahar
6 Du, Donglei
6 Feldman, Vitaly
6 Flammini, Michele
6 Fujito, Toshihiro
6 Grigoriev, Alexander
6 Guruswami, Venkatesan
6 Hassin, Refael
6 Håstad, Johan Torkel
6 Henning, Michael Anthony
6 Khuller, Samir
6 Krivelevich, Michael
6 Kushilevitz, Eyal
6 Lee, James R.
6 Manurangsi, Pasin
6 Marathe, Madhav V.
6 Mehrabian, Abbas
6 Miyano, Eiji
6 Neiman, Ofer
6 Niedermeier, Rolf
6 Noltemeier, Hartmut
6 Nutov, Zeev
6 Pelc, Andrzej
6 Peres, Yuval
6 Rautenbach, Dieter
6 Ravi, Ramamoorthi
6 Salavatipour, Mohammad R.
6 Sau, Ignasi
6 Shachnai, Hadas
...and 2,718 more Authors
all top 5

Cited in 201 Serials

196 Theoretical Computer Science
118 Algorithmica
99 Discrete Applied Mathematics
72 Journal of Combinatorial Optimization
60 Information Processing Letters
58 SIAM Journal on Computing
52 Journal of Computer and System Sciences
44 Mathematical Programming. Series A. Series B
43 Journal of Cryptology
28 SIAM Journal on Discrete Mathematics
25 Operations Research Letters
25 Random Structures & Algorithms
24 Computational Complexity
24 Theory of Computing Systems
22 Information and Computation
22 Journal of Discrete Algorithms
20 Combinatorics, Probability and Computing
19 European Journal of Operational Research
18 Distributed Computing
17 Discrete Mathematics
15 Mathematics of Operations Research
13 Discrete & Computational Geometry
13 Algorithms
12 Artificial Intelligence
12 INFORMS Journal on Computing
11 Journal of Combinatorial Theory. Series B
11 Networks
11 Combinatorica
11 Graphs and Combinatorics
11 Computers & Operations Research
11 Optimization Letters
10 The Annals of Statistics
10 Games and Economic Behavior
9 Discrete Optimization
8 Information Sciences
8 European Journal of Combinatorics
8 Annals of Operations Research
8 Computational Geometry
8 Journal of Global Optimization
8 The Electronic Journal of Combinatorics
7 Journal of Scheduling
7 Journal of Machine Learning Research (JMLR)
7 Discrete Mathematics, Algorithms and Applications
6 Israel Journal of Mathematics
6 Journal of Graph Theory
6 Statistics & Probability Letters
6 Annals of Mathematics and Artificial Intelligence
6 RAIRO. Operations Research
6 Computer Science Review
5 Advances in Mathematics
5 The Annals of Probability
5 Applied Mathematics and Computation
5 Probability Theory and Related Fields
5 International Journal of Computer Mathematics
5 Linear Algebra and its Applications
5 Optimization Methods & Software
5 Journal of the Operations Research Society of China
4 Journal of Statistical Physics
4 Journal of Optimization Theory and Applications
4 Operations Research
4 Optimization
4 International Journal of Approximate Reasoning
4 International Journal of Foundations of Computer Science
4 Bulletin of the American Mathematical Society. New Series
4 SIAM Journal on Optimization
4 Cybernetics and Systems Analysis
4 Computational Optimization and Applications
3 Journal of Combinatorial Theory. Series A
3 Annals of Pure and Applied Logic
3 Designs, Codes and Cryptography
3 International Journal of Computer Vision
3 The Journal of Artificial Intelligence Research (JAIR)
3 Complexity
3 Bernoulli
3 RAIRO. Theoretical Informatics and Applications
3 Electronic Commerce Research
3 Journal of Industrial and Management Optimization
3 Journal of Mathematical Cryptology
3 Electronic Journal of Statistics
3 Science China. Information Sciences
2 Acta Informatica
2 Automatica
2 Journal of the Association for Computing Machinery
2 Journal of Functional Analysis
2 Journal of Automated Reasoning
2 Journal of Theoretical Probability
2 SIAM Journal on Matrix Analysis and Applications
2 Science in China. Series A
2 Machine Learning
2 International Journal of Computational Geometry & Applications
2 The Annals of Applied Probability
2 Proceedings of the National Academy of Sciences of the United States of America
2 Stochastic Processes and their Applications
2 Chicago Journal of Theoretical Computer Science
2 Data Mining and Knowledge Discovery
2 Annals of Mathematics. Second Series
2 Foundations of Computational Mathematics
2 JMMA. Journal of Mathematical Modelling and Algorithms
2 Journal of Applied Mathematics and Computing
2 Quantum Information Processing
...and 101 more Serials
all top 5

Cited in 41 Fields

1,084 Computer science (68-XX)
642 Combinatorics (05-XX)
553 Operations research, mathematical programming (90-XX)
217 Information and communication theory, circuits (94-XX)
149 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
90 Probability theory and stochastic processes (60-XX)
35 Statistics (62-XX)
24 Linear and multilinear algebra; matrix theory (15-XX)
23 Biology and other natural sciences (92-XX)
22 Convex and discrete geometry (52-XX)
20 Numerical analysis (65-XX)
18 Quantum theory (81-XX)
16 Number theory (11-XX)
16 Statistical mechanics, structure of matter (82-XX)
11 Mathematical logic and foundations (03-XX)
11 Functional analysis (46-XX)
7 Calculus of variations and optimal control; optimization (49-XX)
7 General topology (54-XX)
6 Order, lattices, ordered algebraic structures (06-XX)
5 Systems theory; control (93-XX)
4 Group theory and generalizations (20-XX)
4 Real functions (26-XX)
4 Measure and integration (28-XX)
4 Geometry (51-XX)
3 Algebraic geometry (14-XX)
2 General and overarching topics; collections (00-XX)
2 History and biography (01-XX)
2 Approximations and expansions (41-XX)
1 Commutative algebra (13-XX)
1 Potential theory (31-XX)
1 Ordinary differential equations (34-XX)
1 Partial differential equations (35-XX)
1 Dynamical systems and ergodic theory (37-XX)
1 Difference and functional equations (39-XX)
1 Integral transforms, operational calculus (44-XX)
1 Operator theory (47-XX)
1 Differential geometry (53-XX)
1 Algebraic topology (55-XX)
1 Manifolds and cell complexes (57-XX)
1 Global analysis, analysis on manifolds (58-XX)
1 Fluid mechanics (76-XX)

Citations by Year

Wikidata Timeline

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.