×

zbMATH — the first resource for mathematics

Feige, Uriel

Compute Distance To:
Author ID: feige.uriel Recent zbMATH articles by "Feige, Uriel"
Published as: Feige, U.; Feige, Uri; Feige, Uriel
External Links: MGP · Wikidata · dblp
Documents Indexed: 161 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 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 Kogan, Shimon
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 Jain, Kamal C.
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 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 12 more Co-Authors

Publications by Year

Citations contained in zbMATH

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

Cited by 2,666 Authors

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

Cited in 188 Serials

199 Theoretical Computer Science
114 Algorithmica
97 Discrete Applied Mathematics
65 Journal of Combinatorial Optimization
64 Information Processing Letters
50 Journal of Computer and System Sciences
47 SIAM Journal on Computing
43 Mathematical Programming. Series A. Series B
41 Journal of Cryptology
27 Operations Research Letters
26 SIAM Journal on Discrete Mathematics
25 Random Structures & Algorithms
23 Computational Complexity
23 Theory of Computing Systems
22 Journal of Discrete Algorithms
21 Information and Computation
17 European Journal of Operational Research
17 Distributed Computing
16 Discrete Mathematics
14 Combinatorics, Probability and Computing
13 Algorithms
12 Discrete & Computational Geometry
11 Journal of Combinatorial Theory. Series B
11 Mathematics of Operations Research
11 Networks
11 Combinatorica
11 Graphs and Combinatorics
10 Artificial Intelligence
10 Computers & Operations Research
9 The Annals of Statistics
9 INFORMS Journal on Computing
9 Discrete Optimization
9 Optimization Letters
8 Annals of Operations Research
8 Journal of Global Optimization
8 Games and Economic Behavior
7 Information Sciences
7 Computational Geometry
7 Journal of Scheduling
7 Discrete Mathematics, Algorithms and Applications
6 Israel Journal of Mathematics
6 Journal of Graph Theory
6 European Journal of Combinatorics
6 Annals of Mathematics and Artificial Intelligence
6 RAIRO. Operations Research
6 Computer Science Review
5 Advances in Mathematics
5 Applied Mathematics and Computation
5 Statistics & Probability Letters
5 Probability Theory and Related Fields
5 International Journal of Computer Mathematics
5 Linear Algebra and its Applications
5 Journal of the Operations Research Society of China
4 Journal of Statistical Physics
4 Optimization
4 International Journal of Approximate Reasoning
4 International Journal of Foundations of Computer Science
4 SIAM Journal on Optimization
4 Cybernetics and Systems Analysis
4 Computational Optimization and Applications
4 Science China. Information Sciences
3 The Annals of Probability
3 Journal of Optimization Theory and Applications
3 Operations Research
3 Annals of Pure and Applied Logic
3 Designs, Codes and Cryptography
3 Bulletin of the American Mathematical Society. New Series
3 The Electronic Journal of Combinatorics
3 Bernoulli
3 Optimization Methods & Software
3 RAIRO. Theoretical Informatics and Applications
3 Electronic Commerce Research
3 Journal of Machine Learning Research (JMLR)
2 Acta Informatica
2 Automatica
2 Journal of Combinatorial Theory. Series A
2 Journal of Functional Analysis
2 Journal of Automated Reasoning
2 Journal of Theoretical Probability
2 Applied Mathematics Letters
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 International Journal of Computer Vision
2 Complexity
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 Quantum Information Processing
2 Science in China. Series F
2 Journal of Industrial and Management Optimization
2 ALEA. Latin American Journal of Probability and Mathematical Statistics
2 Journal of Mathematical Cryptology
2 Electronic Journal of Statistics
2 Groups, Complexity, Cryptology
...and 88 more Serials
all top 5

Cited in 37 Fields

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