Uriel Feige
Person information
- affiliation: Weizmann Institute of Science, Israel
Refine list

refinements active!
zoomed in on ?? of ?? records
view refined list in
showing all ?? records
2010 – today
- 2018
- [c115]Uriel Feige, Yishay Mansour, Robert E. Schapire:
Robust Inference for Multiclass Classification. ALT 2018: 368-386 - [i37]
- 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. Scheduling 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]
- [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]
- [c107]
- [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 and Economic Behavior 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. Discrete Math. 28(3): 1578-1600 (2014) - [c105]Uriel Feige, Tomer Koren, Moshe Tennenholtz:
Chasing Ghosts: Competing with Stateful Policies. FOCS 2014: 100-109 - [c104]
- [c103]
- [c102]Yossi Azar, Uriel Feige, Michal Feldman, Moshe Tennenholtz:
Sequential decision making with vector outcomes. ITCS 2014: 195-206 - [c101]
- [i31]Uriel Feige, Jonathan Hermon, Daniel Reichman:
On giant components and treewidth in the layers model. CoRR abs/1401.6681 (2014) - [i30]
- [i29]
- [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]
- [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]
- [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]
- [i21]
- [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. Discrete 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]
- [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]
- [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. Discrete 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]
- [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]
- [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]
- 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. Discrete Math. 22(2): 693-718 (2008) - [c81]Arash Asadpour, Uriel Feige, Amin Saberi:
Santa Claus Meets Hypergraph Matchings. APPROX-RANDOM 2008: 10-20 - [c80]
- [c79]
- [c78]
- [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. IEEE Conference on Computational Complexity 2007: 179-192 - [c72]
- [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, Mohammad R. Salavatipour:
Combination can be hard: approximability of the unique coverage problem. SODA 2006: 162-171 - [c65]
- [c64]
- [i7]Uriel Feige, Eran Ofek:
Random 3CNF formulas elude the Lovasz theta function. CoRR abs/cs/0603084 (2006) - [i6]Eran Ofek, Uriel Feige:
Random 3CNF formulas elude the Lovasz theta function. Electronic Colloquium on Computational Complexity (ECCC) 13(043) (2006) - 2005
- [j48]Dan Frumkin, Adam Wasserstrom, Shai Kaplan, Uriel Feige, Ehud Y. Shapiro:
Genomic Variability within an Organism Exposes Its Cell Lineage Tree. PLoS Computational Biology 1(6) (2005) - [j47]Uriel Feige, Eran Ofek:
Spectral techniques applied to sparse random graphs. Random Struct. Algorithms 27(2): 251-275 (2005) - [j46]Eden Chlamtac, Uriel Feige:
Improved approximation of the minimum cover time. Theor. Comput. Sci. 341(1-3): 22-38 (2005) - [c63]
- [c62]Uriel Feige, Eran Ofek:
Finding a Maximum Independent Set in a Sparse Random Graph. APPROX-RANDOM 2005: 282-293 - [c61]
- [c60]Uriel Feige, Mohammad Taghi Hajiaghayi, James R. Lee:
Improved approximation algorithms for minimum-weight vertex separators. STOC 2005: 563-572 - [c59]Uriel Feige, Abraham Flaxman, Jason D. Hartline, Robert D. Kleinberg:
On the Competitive Ratio of the Random Sampling Auction. WINE 2005: 878-886 - [i5]Uriel Feige, Eran Ofek:
Finding a Maximum Independent Set in a Sparse Random Graph. Electronic Colloquium on Computational Complexity (ECCC)(050) (2005) - 2004
- [j45]Uriel Feige, László Lovász, Prasad Tetali:
Approximating Min Sum Set Cover. Algorithmica 40(4): 219-234 (2004) - [j44]Uriel Feige, Daniele Micciancio:
The inapproximability of lattice and coding problems with preprocessing. J. Comput. Syst. Sci. 69(1): 45-67 (2004) - [j43]Uriel Feige, Michael Langberg, Gideon Schechtman:
Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers. SIAM J. Comput. 33(6): 1338-1368 (2004) - [j42]Uriel Feige:
Approximating Maximum Clique by Removing Subgraphs. SIAM J. Discrete Math. 18(2): 219-225 (2004) - [c58]Uriel Feige, Daniel Reichman:
On Systems of Linear Equations with Two Variables per Equation. APPROX-RANDOM 2004: 117-127 - [c57]Uriel Feige, Eran Ofek:
Easily Refutable Subformulas of Large Random 3CNF Formulas. ICALP 2004: 519-530 - [c56]Uriel Feige:
On sums of independent random variables with unbounded variance, and estimating the average degree in a graph. STOC 2004: 594-603 - [i4]