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