# zbMATH — the first resource for mathematics

## Feige, Uriel

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

all top 5

#### Serials

 16 SIAM Journal on Computing 11 Random Structures & Algorithms 8 Algorithmica 8 SIAM Journal on Discrete Mathematics 7 Journal of Computer and System Sciences 6 Information Processing Letters 4 Theoretical Computer Science 3 Journal of Algorithms 3 Computational Complexity 3 Theory of Computing 2 Discrete Applied Mathematics 2 Combinatorica 2 Journal of the ACM 1 Journal of Graph Theory 1 Journal of Cryptology 1 The Annals of Applied Probability 1 Games and Economic Behavior 1 SIAM Review 1 Distributed Computing 1 Theory of Computing Systems 1 Chicago Journal of Theoretical Computer Science 1 Journal of Scheduling 1 ACM Transactions on Algorithms
all top 5

#### Fields

 126 Computer science (68-XX) 60 Combinatorics (05-XX) 42 Operations research, mathematical programming (90-XX) 18 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 14 Probability theory and stochastic processes (60-XX) 8 Information and communication theory, circuits (94-XX) 2 Mathematical logic and foundations (03-XX) 2 Linear and multilinear algebra; matrix theory (15-XX) 2 Measure and integration (28-XX) 2 Statistics (62-XX) 1 Numerical analysis (65-XX)

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

#### Wikidata Timeline

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