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