Google
Google Scholar
MS Academic
CiteSeerX
CORE
Semantic ScholarUriel Feige
Person information
- affiliation: Weizmann Institute of Science, Israel
- award (2001): Gödel Prize
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2020
[j84]Uriel Feige, David Gamarnik, Joe Neeman, Miklós Z. Rácz, Prasad Tetali:
Finding cliques using few probes. Random Struct. Algorithms 56(1): 142-153 (2020)- [j83]Uriel Feige, Michal Feldman, Inbal Talgam-Cohen:
Approximate Modularity Revisited. SIAM J. Comput. 49(1): 67-97 (2020) - [j82]Uriel Feige, Anne Kenyon, Shimon Kogan:
On the Profile of Multiplicities of Complete Subgraphs. SIAM J. Discret. Math. 34(1): 950-971 (2020) - [i46]Moshe Babaioff, Tomer Ezra, Uriel Feige:
Fair and Truthful Mechanisms for Dichotomous Valuations. CoRR abs/2002.10704 (2020) - [i45]Uriel Feige, Vadim Grinberg:
How to hide a clique? CoRR abs/2004.12258 (2020)
2010 – 2019
- 2019
- [c120]Alon Eden, Uriel Feige, Michal Feldman:
Max-Min Greedy Matching. APPROX-RANDOM 2019: 7:1-7:23 - [c119]Alon Eden, Uriel Feige, Michal Feldman:
Max-min greedy matching. NetEcon@SIGMETRICS 2019: 10:1 - [c118]Uriel Feige, Janardhan Kulkarni, Shi Li:
A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time. SODA 2019: 1585-1595 - [c117]Moshe Babaioff, Uriel Feige:
A New Approach to Fair Distribution of Welfare. WINE 2019: 71-84 - [i44]Uriel Feige:
A randomized strategy in the mirror game. CoRR abs/1901.07809 (2019) - [i43]Uriel Feige, Shimon Kogan:
Target Set Selection for Conservative Populations. CoRR abs/1909.03422 (2019) - [i42]Moshe Babaioff, Uriel Feige:
A New Approach to Fair Distribution of Welfare. CoRR abs/1909.11346 (2019) - [i41]Uriel Feige, Ella Fuchs:
On the path partition number of 6-regular graphs. CoRR abs/1911.08397 (2019) - 2018
- [j81]Uriel Feige, Yael Hitron
:
The Ordered Covering Problem. Algorithmica 80(10): 2874-2908 (2018) - [j80]Roee David, Uriel Feige:
Random Walks with the Minimum Degree Local Rule Have O(n2) Cover Time. SIAM J. Comput. 47(3): 755-768 (2018) - [c116]Uriel Feige, Yishay Mansour, Robert E. Schapire:
Robust Inference for Multiclass Classification. ALT 2018: 368-386 - [c115]Uriel Feige, Boaz Patt-Shamir, Shai Vardi:
On the Probe Complexity of Local Computation Algorithms. ICALP 2018: 50:1-50:14 - [i40]Alon Eden, Uriel Feige, Michal Feldman:
Max-Min Greedy Matching. CoRR abs/1803.05501 (2018) - [i39]Uriel Feige, Janardhan Kulkarni, Shi Li:
A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time. CoRR abs/1807.09885 (2018) - [i38]Uriel Feige, David Gamarnik, Joe Neeman, Miklós Z. Rácz, Prasad Tetali:
Finding cliques using few probes. CoRR abs/1809.06950 (2018) - [i37]Uriel Feige:
Tighter bounds for online bipartite matching. CoRR abs/1812.11774 (2018) - 2017
- [j79]Uriel Feige, Moshe Tennenholtz:
Optimization with Uniform Size Queries. Algorithmica 78(1): 255-273 (2017) - [j78]Marek Chrobak, Uriel Feige, Mohammad Taghi Hajiaghayi, Sanjeev Khanna, Fei Li, Seffi Naor:
A greedy approximation algorithm for minimum-gap scheduling. J. Sched. 20(3): 279-292 (2017) - [j77]Uriel Feige, Tomer Koren, Moshe Tennenholtz:
Chasing Ghosts: Competing with Stateful Policies. SIAM J. Comput. 46(1): 190-223 (2017) - [c114]Roee David, Uriel Feige:
Random Walks with the Minimum Degree Local Rule Have O(N2) Cover Time. SODA 2017: 1839-1848 - [c113]Uriel Feige, Michal Feldman, Inbal Talgam-Cohen:
Approximate modularity revisited. STOC 2017: 1028-1041 - [i36]Uriel Feige, Boaz Patt-Shamir, Shai Vardi:
On the Probe Complexity of Local Computation Algorithms. CoRR abs/1703.07734 (2017) - 2016
- [j76]Uriel Feige, Jonathan Hermon, Daniel Reichman:
On giant components and treewidth in the layers model. Random Struct. Algorithms 48(3): 524-545 (2016) - [c112]Uriel Feige, Michal Feldman, Inbal Talgam-Cohen:
Oblivious Rounding and the Integrality Gap. APPROX-RANDOM 2016: 8:1-8:23 - [c111]Roee David, Uriel Feige:
On the effect of randomness on planted 3-coloring models. STOC 2016: 77-90 - [i35]Roee David, Uriel Feige:
On the effect of randomness on planted 3-coloring models. CoRR abs/1603.05183 (2016) - [i34]Roee David, Uriel Feige:
Random walks with the minimum degree local rule have $O(n^2)$ cover time. CoRR abs/1604.08326 (2016) - [i33]Charles Bordenave, Uriel Feige, Elchanan Mossel:
Shotgun Assembly of Random Jigsaw Puzzles. CoRR abs/1605.03086 (2016) - [i32]Uriel Feige, Michal Feldman, Inbal Talgam-Cohen:
Approximate Modularity Revisited. CoRR abs/1612.02034 (2016) - 2015
- [j75]Uriel Feige, Shlomo Jozeph:
Oblivious Algorithms for the Maximum Directed Cut Problem. Algorithmica 71(2): 409-428 (2015) - [j74]Uriel Feige, Daniel Reichman:
Recoverable values for independent sets. Random Struct. Algorithms 46(1): 142-159 (2015) - [c110]Uriel Feige, Michal Feldman, Nicole Immorlica, Rani Izsak, Brendan Lucier, Vasilis Syrgkanis:
A Unifying Hierarchy of Valuations with Complements and Substitutes. AAAI 2015: 872-878 - [c109]Uriel Feige, Yishay Mansour, Robert E. Schapire:
Learning and inference in the presence of corrupted inputs. COLT 2015: 637-657 - [c108]Uriel Feige:
Why are Images Smooth? ITCS 2015: 229-236 - [c107]Uriel Feige, Shlomo Jozeph:
Separation between Estimation and Approximation. ITCS 2015: 271-276 - [c106]Amin Coja-Oghlan, Uriel Feige, Michael Krivelevich, Daniel Reichman:
Contagious Sets in Expanders. SODA 2015: 1953-1987 - 2014
- [j73]Uriel Feige, Moshe Tennenholtz:
On fair division of a homogeneous good. Games Econ. Behav. 87: 305-321 (2014) - [j72]Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz:
Min-Max Graph Partitioning and Small Set Expansion. SIAM J. Comput. 43(2): 872-904 (2014) - [j71]Yehuda Afek, Yakov Babichenko, Uriel Feige, Eli Gafni, Nati Linial, Benny Sudakov:
Musical Chairs. SIAM J. Discret. Math. 28(3): 1578-1600 (2014) - [c105]Uriel Feige, Tomer Koren, Moshe Tennenholtz:
Chasing Ghosts: Competing with Stateful Policies. FOCS 2014: 100-109 - [c104]Uriel Feige, Shlomo Jozeph:
Demand Queries with Preprocessing. ICALP (1) 2014: 477-488 - [c103]Uriel Feige, Moshe Tennenholtz:
Invitation games and the price of stability. ITCS 2014: 93-102 - [c102]Yossi Azar, Uriel Feige, Michal Feldman, Moshe Tennenholtz:
Sequential decision making with vector outcomes. ITCS 2014: 195-206 - [c101]Uriel Feige, R. Ravi, Mohit Singh:
Short Tours through Large Linear Forests. IPCO 2014: 273-284 - [i31]Uriel Feige, Jonathan Hermon, Daniel Reichman:
On giant components and treewidth in the layers model. CoRR abs/1401.6681 (2014) - [i30]Uriel Feige:
On robustly asymmetric graphs. CoRR abs/1402.1047 (2014) - [i29]Uriel Feige:
Why are images smooth? CoRR abs/1406.5035 (2014) - [i28]Uriel Feige, Tomer Koren, Moshe Tennenholtz:
Chasing Ghosts: Competing with Stateful Policies. CoRR abs/1407.7635 (2014) - [i27]Uriel Feige, Michal Feldman, Nicole Immorlica, Rani Izsak, Brendan Lucier, Vasilis Syrgkanis:
A Unifying Hierarchy of Valuations with Complements and Substitutes. CoRR abs/1408.1211 (2014) - [i26]Uriel Feige:
NP-hardness of hypercube 2-segmentation. CoRR abs/1411.0821 (2014) - [i25]Uriel Feige, Michal Feldman, Nicole Immorlica, Rani Izsak, Brendan Lucier, Vasilis Syrgkanis:
A Unifying Hierarchy of Valuations with Complements and Substitutes. Electronic Colloquium on Computational Complexity (ECCC) 21: 103 (2014) - [i24]Uriel Feige, Shlomo Jozeph:
Separation between Estimation and Approximation. Electronic Colloquium on Computational Complexity (ECCC) 21: 110 (2014) - 2013
- [j70]Uriel Feige, Nicole Immorlica, Vahab S. Mirrokni, Hamid Nazerzadeh:
PASS Approximation: A Framework for Analyzing and Designing Heuristics. Algorithmica 66(2): 450-478 (2013) - [j69]Uriel Feige, Elchanan Mossel, Dan Vilenchik:
Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems. Theory of Computing 9: 617-651 (2013) - [c100]Uriel Feige, Gil Kalai, Moshe Tennenholtz:
The Cascade Auction - A Mechanism for Deterring Collusion in Auctions. AAAI 2013 - [c99]Roee David, Uriel Feige:
Connectivity of Random High Dimensional Geometric Graphs. APPROX-RANDOM 2013: 497-512 - [c98]Marek Chrobak, Uriel Feige, Mohammad Taghi Hajiaghayi, Sanjeev Khanna, Fei Li, Seffi Naor:
A Greedy Approximation Algorithm for Minimum-Gap Scheduling. CIAC 2013: 97-109 - [c97]Uriel Feige, Rani Izsak:
Welfare maximization and the supermodular degree. ITCS 2013: 247-256 - [c96]Uriel Feige, Ron Lavi, Moshe Tennenholtz:
Competition among asymmetric sellers with fixed supply. EC 2013: 415-416 - [i23]Amin Coja-Oghlan, Uriel Feige, Michael Krivelevich, Daniel Reichman:
Contagious Sets in Expanders. CoRR abs/1306.2465 (2013) - [i22]Uriel Feige, Rani Izsak:
Welfare Maximization and the Supermodular Degree. Electronic Colloquium on Computational Complexity (ECCC) 20: 95 (2013) - 2012
- [j68]Arash Asadpour, Uriel Feige, Amin Saberi:
Santa claus meets hypergraph matchings. ACM Trans. Algorithms 8(3): 24:1-24:9 (2012) - [c95]Yossi Azar, Uriel Feige, Moshe Tennenholtz, Michal Feldman:
Mastering multi-player games. AAMAS 2012: 897-904 - [c94]Uriel Feige, Shlomo Jozeph:
Universal Factor Graphs. ICALP (1) 2012: 339-350 - [i21]Uriel Feige, Shlomo Jozeph:
Universal Factor Graphs. CoRR abs/1204.6484 (2012) - [i20]Yehuda Afek, Yakov Babichenko, Uriel Feige, Eli Gafni, Nati Linial, Benny Sudakov:
Musical chairs. CoRR abs/1208.0813 (2012) - 2011
- [j67]Chandan K. Dubey, Uriel Feige, Walter Unger:
Hardness results for approximating the bandwidth. J. Comput. Syst. Sci. 77(1): 62-90 (2011) - [j66]Yossi Azar, Uriel Feige, Iftah Gamzu, Thomas Moscibroda, Prasad Raghavendra:
Buffer Management for Colored Packets with Deadlines. Theory Comput. Syst. 49(4): 738-756 (2011) - [j65]Uriel Feige, Vahab S. Mirrokni, Jan Vondrák:
Maximizing Non-monotone Submodular Functions. SIAM J. Comput. 40(4): 1133-1153 (2011) - [j64]Uriel Feige, Abraham D. Flaxman, Dan Vilenchik:
On the Diameter of the Set of Satisfying Assignments in Random Satisfiable k-CNF Formulas. SIAM J. Discret. Math. 25(2): 736-749 (2011) - [c93]Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz:
Min-max Graph Partitioning and Small Set Expansion. FOCS 2011: 17-26 - [c92]Uriel Feige, Daniel Reichman:
Recoverable Values for Independent Sets. ICALP (1) 2011: 486-497 - [c91]Uriel Feige, Moshe Tennenholtz:
Mechanism design with uncertain inputs: (to err is human, to forgive divine). STOC 2011: 549-558 - [c90]Nikhil R. Devanur, Uriel Feige:
An O(n log n) Algorithm for a Load Balancing Problem on Paths. WADS 2011: 326-337 - [c89]Yehuda Afek, Yakov Babichenko, Uriel Feige, Eli Gafni, Nati Linial, Benny Sudakov:
Oblivious Collaboration. DISC 2011: 489-504 - [i19]Uriel Feige, Moshe Tennenholtz:
Mechanism design with uncertain inputs (to err is human, to forgive divine). CoRR abs/1103.2520 (2011) - [i18]Uriel Feige, Daniel Reichman:
Recoverable Values for Independent Sets. CoRR abs/1103.5609 (2011) - [i17]Yehuda Afek, Yakov Babichenko, Uriel Feige, Eli Gafni, Nati Linial, Benny Sudakov:
Oblivious Collaboration. CoRR abs/1106.2065 (2011) - [i16]Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz:
Min-Max Graph Partitioning and Small Set Expansion. CoRR abs/1110.4319 (2011) - [i15]Martin E. Dyer, Uriel Feige, Alan M. Frieze, Marek Karpinski:
Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241). Dagstuhl Reports 1(6): 24-53 (2011) - 2010
- [j63]Yossi Azar, Uriel Feige, Daniel Glasner:
A Preemptive Algorithm for Maximizing Disjoint Paths on Trees. Algorithmica 57(3): 517-537 (2010) - [j62]Uriel Feige, Shimon Kogan:
Balanced coloring of bipartite graphs. Journal of Graph Theory 64(4): 277-291 (2010) - [j61]Uriel Feige:
On Optimal Strategies for a Hat Game on Graphs. SIAM J. Discret. Math. 24(3): 782-791 (2010) - [j60]Uriel Feige, Jan Vondrák:
The Submodular Welfare Problem with Demand Queries. Theory of Computing 6(1): 247-290 (2010) - [c88]Uriel Feige, Inbal Talgam-Cohen:
A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium. SAGT 2010: 138-149 - [c87]Uriel Feige, Moshe Tennenholtz:
Responsive Lotteries. SAGT 2010: 150-161 - [c86]Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, Aravindan Vijayaraghavan:
Detecting high log-densities: an O(n1/4) approximation for densest k-subgraph. STOC 2010: 201-210 - [i14]Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, Aravindan Vijayaraghavan:
Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph. CoRR abs/1001.2891 (2010) - [i13]Uriel Feige, Inbal Talgam-Cohen:
A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium. CoRR abs/1007.3886 (2010) - [i12]Uriel Feige, Shlomo Jozeph:
Oblivious Algorithms for the Maximum Directed Cut Problem. CoRR abs/1010.0406 (2010)
2000 – 2009
- 2009
- [j59]Uriel Feige, Kunal Talwar:
Approximating the Bandwidth of Caterpillars. Algorithmica 55(1): 190-204 (2009) - [j58]Uriel Feige:
On Maximizing Welfare When Utility Functions Are Subadditive. SIAM J. Comput. 39(1): 122-142 (2009) - [c85]Uriel Feige, Nicole Immorlica, Vahab S. Mirrokni, Hamid Nazerzadeh:
PASS Approximation. APPROX-RANDOM 2009: 111-124 - [c84]Noga Alon, Uriel Feige:
On the power of two, three and four probes. SODA 2009: 346-354 - [c83]Amin Coja-Oghlan, Uriel Feige, Alan M. Frieze, Michael Krivelevich, Dan Vilenchik:
On smoothed k-CNF formulas and the Walksat algorithm. SODA 2009: 451-460 - [c82]Yossi Azar, Uriel Feige, Iftah Gamzu, Thomas Moscibroda, Prasad Raghavendra:
Buffer management for colored packets with deadlines. SPAA 2009: 319-327 - [i11]Reid Andersen, Uriel Feige:
Interchanging distance and capacity in probabilistic mappings. CoRR abs/0907.3631 (2009) - [i10]Uriel Feige, Ofer Zeitouni:
Deterministic approximation for the cover time of trees. CoRR abs/0909.2005 (2009) - [i9]Uriel Feige:
Faster FAST(Feedback Arc Set in Tournaments). CoRR abs/0911.5094 (2009) - 2008
- [j57]Uriel Feige, MohammadTaghi Hajiaghayi, James R. Lee:
Improved Approximation Algorithms for Minimum Weight Vertex Separators. SIAM J. Comput. 38(2): 629-657 (2008) - [j56]Erik D. Demaine, Uriel Feige, MohammadTaghi Hajiaghayi, Mohammad R. Salavatipour:
Combination Can Be Hard: Approximability of the Unique Coverage Problem. SIAM J. Comput. 38(4): 1464-1483 (2008) - [j55]Uriel Feige, Eran Ofek:
Finding a Maximum Independent Set in a Sparse Random Graph. SIAM J. Discret. Math. 22(2): 693-718 (2008) - [c81]Arash Asadpour, Uriel Feige, Amin Saberi:
Santa Claus Meets Hypergraph Matchings. APPROX-RANDOM 2008: 10-20 - [c80]Uriel Feige, Mohit Singh:
Edge Coloring and Decompositions of Weighted Graphs. ESA 2008: 405-416 - [c79]Uriel Feige:
On Estimation Algorithms vs Approximation Algorithms. FSTTCS 2008: 357-363 - [c78]Uriel Feige:
On allocations that maximize fairness. SODA 2008: 287-293 - [c77]Yossi Azar, Uriel Feige, Daniel Glasner:
A Preemptive Algorithm for Maximizing Disjoint Paths on Trees. SWAT 2008: 319-330 - [c76]Uriel Feige, Nicole Immorlica, Vahab S. Mirrokni, Hamid Nazerzadeh:
A combinatorial allocation mechanism with penalties for banner advertising. WWW 2008: 169-178 - [c75]Reid Andersen, Christian Borgs, Jennifer T. Chayes, Uriel Feige, Abraham D. Flaxman, Adam Kalai, Vahab S. Mirrokni, Moshe Tennenholtz:
Trust-based recommendation systems: an axiomatic approach. WWW 2008: 199-208 - 2007
- [j54]Uriel Feige, James R. Lee:
An improved approximation ratio for the minimum linear arrangement problem. Inf. Process. Lett. 101(1): 26-29 (2007) - [j53]Uriel Feige, Eran Ofek:
Easily refutable subformulas of large random 3CNF formulas. Theory of Computing 3(1): 25-43 (2007) - [c74]Uriel Feige, Mohit Singh:
Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs. APPROX-RANDOM 2007: 104-118 - [c73]Uriel Feige, Guy Kindler, Ryan O'Donnell:
Understanding Parallel Repetition Requires Understanding Foams. Computational Complexity Conference 2007: 179-192 - [c72]Uriel Feige:
Refuting Smoothed 3CNF Formulas. FOCS 2007: 407-417 - [c71]Uriel Feige, Vahab S. Mirrokni, Jan Vondrák:
Maximizing Non-Monotone Submodular Functions. FOCS 2007: 461-471 - [c70]Uriel Feige, Kamal Jain, Mohammad Mahdian, Vahab S. Mirrokni:
Robust Combinatorial Optimization with Exponential Scenarios. IPCO 2007: 439-453 - [e1]David S. Johnson, Uriel Feige:
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007. ACM 2007, ISBN 978-1-59593-631-8 [contents] - [i8]Uriel Feige, Guy Kindler, Ryan O'Donnell:
Understanding Parallel Repetition Requires Understanding Foams. Electronic Colloquium on Computational Complexity (ECCC) 14(043) (2007) - 2006
- [j52]Uriel Feige, Daniel Reichman:
On the hardness of approximating Max-Satisfy. Inf. Process. Lett. 97(1): 31-35 (2006) - [j51]Uriel Feige, Michael Langberg:
The RPR2 rounding technique for semidefinite programs. J. Algorithms 60(1): 1-23 (2006) - [j50]Uriel Feige:
On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph. SIAM J. Comput. 35(4): 964-984 (2006) - [j49]Robert Krauthgamer, Uriel Feige:
A Polylogarithmic Approximation of the Minimum Bisection. SIAM Review 48(1): 99-130 (2006) - [c69]Uriel Feige, Elchanan Mossel, Dan Vilenchik:
Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems. APPROX-RANDOM 2006: 339-350 - [c68]Uriel Feige, Jeong Han Kim, Eran Ofek:
Witnesses for non-satisfiability of dense random 3CNF formulas. FOCS 2006: 497-508 - [c67]Uriel Feige, Jan Vondrák:
Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e. FOCS 2006: 667-676 - [c66]Erik D. Demaine, Mohammad Taghi Hajiaghayi, Uriel Feige,