Recent publications

Publications since 2007

  1. Uriel Feige and Eran Ofek.
    Easily refutable subformulas of large random 3CNF formulas
    Theory of Computing, Volume 3 (2007) Article 2, pp. 25-43.
    Version: May 2006.
  2. Uriel Feige.
    On maximizing welfare when utility functions are subadditive
    SICOMP 39(1): 122-142 (2009). Preliminary version in 38th STOC, 2006, 41-50.
    Version: October 2007.
  3. Uriel Feige.
    On Allocations that Maximize Fairness
    SODA 2008, 287-293.
    Version: October 2007.
  4. Uriel Feige and Eran Ofek.
    Finding a Maximum Independent Set in a Sparse Random Graph
    SIAM Journal on Discrete Mathematics, Volume 22(2), 693-718 (2008).
    Version: December 2007.
  5. Uriel Feige, Nicole Immorlica, Vahab Mirrokni and Hamid Nazerzadeh.
    A Combinatorial Allocation Mechanism With Penalties For Banner Advertising
    Proceedings of the 17th International World Wide Web Conference, 169-178, 2008.
    Version: February 2008.
  6. Reid Andersen, Christian Borgs, Jennifer Chayes, Uriel Feige, Abraham Flaxman, Adam Kalai, Vahab Mirrokni and Moshe Tennenholtz.
    Trust-based recommendation systems: an axiomatic approach
    Proceedings the 17th International World Wide Web Conference, 199-208, 2008.
    Version: February 2008.
  7. Arash Asadpour, Uriel Feige and Amin Saberi.
    Santa Claus Meets Hypergraph Matchings
    ACM Transactions on Algorithms 8(3): 24 (2012). Preliminary version in proceedings of APPROX-RANDOM 2008: 10-20.
    Version: June 2008.
  8. Uriel Feige and Mohit Singh.
    Edge coloring and decompositions of weighted graphs
    Proceedings of ESA 2008: 405-416.
    Version: June 2008.
  9. Uriel Feige.
    Small linear dependencies for binary vectors of low weight
    In Building Bridges Between Mathematics and Computer Science, Bolyai Society Mathematical Studies, 19, Springer. Editors: Martin Grotschel and Gyula Katona. Pages 283-307, 2008.
    Version: June 2008.
  10. Noga Alon and Uriel Feige.
    On the power of two, three and four probes
    Proceedings of SODA 2009, 346-354.
    Version: December 2008.
  11. Amin Coja-Oghlan, Uriel Feige, Alan Frieze, Michael Krivelevich and Dan Vilenchik.
    On smoothed k-CNF formulas and the Walksat algorithm
    Proceedings of SODA 2009, 451-460.
    Version: October 2008.
  12. Yossi Azar, Uriel Feige and Daniel Glasner.
    A preemptive algorithm for maximizing disjoint paths on trees
    Algorithmica 57(3): 517-537 (2010). Preliminary version in Proceedings of SWAT 2008: 319-330.
    Version: October 2008.
  13. Uriel Feige, Elchanan Mossel and Dan Vilenchik.
    Complete convergence of message passing algorithms for some satisfiability problems
    Theory of computing, Volume 9 (2013) Article 19 pp. 617-651. Preliminary version in Proceedings of APPROX-RANDOM 2006: 339-350.
    Version: May 2013.
  14. Uriel Feige, Abraham Flaxman and 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).
    Version: December 2008.
  15. Yossi Azar, Uriel Feige, Iftah Gamzu, Thomas Moscibroda and Prasad Raghavendra.
    Buffer Management for Colored Packets with Deadlines
    Proceedings of SPAA 2009, 319-327.
    Version: May 2009.
  16. Chandan Dubey, Uriel Feige and Walter Unger.
    Hardness results for approximating the bandwidth
    J. Comput. Syst. Sci. 77(1): 62-90 (2011)
    Version: June 2009.
  17. Uriel Feige and Shimon Kogan.
    Balanced coloring of bipartite graphs
    Journal of Graph Theory, Volume 64, Number 4, pages 277-291.
    Version: June 2009.
  18. Reid Andersen and Uriel Feige.
    Interchanging distance and capacity in probabilistic mappings
    In arxiv.org.
    Version: July 2009.
  19. Uriel Feige, Nicole Immorlica, Vahab S. Mirrokni, Hamid Nazerzadeh.
    PASS Approximation: A Framework for Analyzing and Designing Heuristics
    Algorithmica 66(2): 450-478 (2013). Preliminary version appeared in proceedings of APPROX 2009, 111-124.
    Version: August 2009.
  20. Uriel Feige and Ofer Zeitouni.
    Deterministic approximation for the cover time of trees
    In arxiv.org.
    Version: September 2009.
  21. Uriel Feige.
    Faster FAST (Feedback Arc Set in Tournaments)
    In arxiv.org.
    Version: November 2009.
  22. Uriel Feige.
    On optimal strategies for a hat game on graphs
    SIAM J. Discrete Math. 24(3): 782-791 (2010).
    Version: April 2010.
  23. Uriel Feige, Vahab Mirrokni, Jan Vondrak.
    Maximizing non-monotone submodular functions
    SIAM J. Comput. 40(4): 1133-1153 (2011).
    Version: December 2009.
  24. Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, Aravindan Vijayaraghavan.
    Detecting High Log-Densities - an O(n^1/4) Approximation for Densest k-Subgraph
    In arxiv.org. Proceedings of STOC 2010.
    Version: January 2010.
  25. Uriel Feige and Dorit Ron.
    Finding hidden cliques in linear time.
    Proceedings of AOFA 2010.
    Version: May 2010.
  26. Uriel Feige and Inbal Talgam-Cohen.
    A direct reduction from k-player to 2-player approximate Nash equilibrium.
    In arxiv.org. SAGT 2010: 138-149.
    Version: July 2010.
  27. Uriel Feige and Shlomo Jozeph.
    Oblivious Algorithms for the Maximum Directed Cut Problem.
    In arxiv.org.
    Version: October 2010.
  28. Yehuda Afek, Yakov Babichenko, Uriel Feige, Eli Gafni, Nati Linial, Benny Sudakov.
    Oblivious collaboration.
    In arxiv.org. DISC 2011.
    Version: March 2011. Closely related to [55].
  29. Uriel Feige and Moshe Tennenholtz.
    Responsive lotteries.
    Proceedings of SAGT 2010: 150-161.
    Version: March 2011.
  30. Uriel Feige and Moshe Tennenholtz.
    Mechanism design with uncertain inputs (to err is human, to forgive divine).
    In arxiv.org. STOC 2011: 549-558.
    Version: March 2011. Closely related to [49].
  31. Uriel Feige and Daniel Reichman.
    Recoverable values for independent sets.
    In arxiv.org. ICALP (1) 2011: 486-497.
    Version: March 2011.
  32. Nikhil Devanur and Uriel Feige.
    An O(n log n) Algorithm for a Load Balancing Problem on Paths.
    WADS 2011: 326-337.
    Version: February 2011.
  33. Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph (Seffi) Naor, Roy Schwartz.
    Min-Max Graph Partitioning and Small Set Expansion.
    SIAM J. Comput. 43(2): 872-904 (2014). Preliminary version in FOCS 2011: 17-26.
    Version: May 2014.
  34. Yossi Azar, Uriel Feige, Michal Feldman, Moshe Tennenholtz.
    Mastering multi-player games.
    Proceedings of AAMAS 2012: 897-904.
  35. Uriel Feige and Shlomo Jozeph.
    Universal factor graphs.
    In arxiv.org. ICALP (1) 2012: 339-350.
    Version: April 2012.
  36. Uriel Feige and Rani Izsak.
    Welfare Maximization and the Supermodular Degree.
    ITCS 2013: 247-256.
    Version: February 2013.
  37. 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.
    Version: January 2013.
  38. Uriel Feige, Ron Lavi, Moshe Tennenholtz
    Competition Among Asymmetric Sellers With Fixed Supply.
    EC 2013: 415-416.
    Version: May 2013.
  39. Uriel Feige, Gil Kalai, Moshe Tennenholtz
    The cascade auction - a mechanism for deterring collusion in auctions.
    AAAI 2013.
    Version: April 2013.
  40. Amin Coja-Oghlan, Uriel Feige, Michael Krivelevich, Daniel Reichman
    Contagious Sets in Expanders.
    In arxiv.org.
    Version: February 2014. Closely related to [54].
  41. Roee David, Uriel Feige
    Connectivity of Random High Dimensional Geometric Graphs.
    APPROX-RANDOM 2013: 497-512.
    Version: June 2013.
  42. Yossi Azar, Uriel Feige, Michal Feldman, Moshe Tennenholtz.
    Sequential Decision Making with Vector Outcomes.
    ITCS 2014: 195-206.
    Version: December 2013.
  43. Uriel Feige and Moshe Tennenholtz
    Invitation Games and the Price of Stability.
    ITCS 2014: 93-102.
    Version: December 2013.
  44. Uriel Feige, Jonathan Hermon and Daniel Reichman
    On giant components and treewidth in the layers model.
    Random Struct. Algorithms 48(3): 524-545 (2016).
    Version: February 2014.
  45. Uriel Feige
    On robustly asymmetric graphs.
    In arxiv.org.
    Version: February 2014.
  46. Jonathan Blakes, Ofir Raz, Uriel Feige, Jaume Bacardit, Pawel Widera, Tuval Ben-Yehezkel, Ehud Shapiro, and Natalio Krasnogor
    A heuristic for maximizing DNA reuse in synthetic DNA library assembly.
    ACS Synthetic Biology.
    Version: February 2014.
  47. Uriel Feige and Shlomo Jozeph
    Demand Queries with Preprocessing.
    ICALP (1) 2014: 477-488.
    Version: May 2014.
  48. Uriel Feige
    Why are images smooth?
    ITCS 2015.
    Version: June 2014.
  49. Uriel Feige and Moshe Tennenholtz
    On fair division of a homogeneous good.
    Games and Economic Behavior 87: 305-321 (2014).
    Version: February 2014. Closely related to [30].
  50. Uriel Feige, R. Ravi and Mohit Singh.
    Short Tours through Large Linear Forests.
    IPCO 2014: 273-284.
    Version: April 2014.
  51. Uriel Feige, Tomer Koren and Moshe Tennenholtz
    Chasing Ghosts: Competing with Stateful Policies.
    FOCS 2014. SICOMP 2017.
    Version: February 2017.
  52. Uriel Feige, Michal Feldman, Nicole Immorlica, Rani Izsak, Brendan Lucier and Vasilis Syrgkanis
    A Unifying Hierarchy of Valuations with Complements and Substitutes.
    AAAI 2015.
    Version: August 2014.
  53. Uriel Feige and Shlomo Jozeph
    Separation between Estimation and Approximation.
    ITCS 2015. ECCC report TR14-110.
    Version: August 2014.
  54. Uriel Feige, Michael Krivelevich and Daniel Reichman
    Contagious Sets in Random Graphs
    Annals of Applied Probability, 2017.
    Version: July 2016. Closely related to [40].
  55. Yehuda Afek, Yakov Babichenko, Uriel Feige, Eli Gafni, Nati Linial, Benny Sudakov.
    Musical chairs.
    SIAM Journal on Discrete Mathematics (Vol. 28, Issue 3) 2014.
    Version: October 2014. Closely related to [28].
  56. Uriel Feige.
    NP-hardness of hypercube 2-segmentation.
    In arxiv.org.
    Version: November 2014.
  57. Uriel Feige, Yishay Mansour, Robert E. Schapire.
    Learning and inference in the presence of corrupted inputs.
    COLT 2015: 637-657.
    Version: June 2015.
  58. Uriel Feige and Moshe Tennenholtz.
    Optimization with uniform size queries.
    Algorithmica, 2017.
    Version: May 2015.
  59. Roee David and Uriel Feige.
    On the effect of randomness on planted 3-coloring models
    STOC 2016.
    Version: March 2016.
  60. Roee David and Uriel Feige.
    Random walks with the minimum degree local rule have O(n^2) cover time
    SODA 2017, Sicomp 2018.
    Version: April 2016.
  61. Charles Bordenave, Uriel Feige, Elchanan Mossel.
    Shotgun Assembly of Random Jigsaw Puzzles
    Random Structures and Algorithms 2020.
    Version: May 2016.
  62. Uriel Feige, Michal Feldman, Inbal Talgam-Cohen.
    Oblivious Rounding and the Integrality Gap.
    Approx 2016.
    Version: June 2016.
  63. Uriel Feige and Tal Wagner.
    Generalized Girth Problems in Graphs and Hypergraphs.
    Submitted.
    Version: July 2016.
  64. Uriel Feige and Yael Hitron.
    The ordered covering problem.
    Algorithmica 2018.
    Version: August 2017.
  65. Uriel Feige, Michal Feldman, Inbal Talgam-Cohen.
    Approximate Modularity Revisited.
    STOC 2017, Sicomp 2020.
    Version: March 2018.
  66. Uriel Feige, Boaz Patt-Shamir, Shai Vardi.
    On the Probe Complexity of Local Computation Algorithms.
    ICALP 2018.
    Version: March 2017.
  67. Uriel Feige, Anne Kenyon, Shimon Kogan.
    On the Profile of Multiplicities of Complete Subgraphs.
    SIAM J. Discrete Math., 34(1), 950-971, 2020.
    Version: January 2019.
  68. Alon Eden, Uriel Feige, Michal Feldman
    Max-Min Greedy Matching.
    Approx 2019.
    Version: March 2018.
  69. Uriel Feige
    Tighter bounds for online bipartite matching.
    In Building Bridges II: Mathematics of Laszlo Lovasz. Bolyai Society Mathematical Studies 28, Springer. Editors: Barany, Imre, Katona, Gyula O. H., Sali, Attila. Pages 235-255, 2019.
    Version: December 2018.
  70. Uriel Feige, Yishay Mansour, Robert E. Schapire.
    Robust Inference for Multiclass Classification.
    ALT 2018: 368-386.
    Version: February 2018.
  71. Uriel Feige, Janardhan Kulkarni, Shi Li.
    A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time.
    SODA 2019.
    Version: July 2018.
  72. Uriel Feige, David Gamarnik, Joe Neeman, Miklos Z. Racz, Prasad Tetali.
    Finding cliques using few probes.
    Random Structures and Algorithms, 2020.
    Version: September 2018.
  73. Uriel Feige.
    A randomized strategy in the mirror game.
    In arxiv.org.
    Version: January 2019.
  74. Moshe Babaioff, Uriel Feige.
    A New Approach to Fair Distribution of Welfare.
    WINE 2019.
    Version: September 2019.
  75. Uriel Feige, Shimon Kogan.
    Target Set Selection for Conservative Populations.
    Discret. Appl. Math 2021.
    Version: September 2019.
  76. Uriel Feige, Ella Fuchs.
    On the path partition number of 6-regular graphs
    Journal of Graph Theory 2022.
    Version: November 2019.
  77. Lucas Boczkowski, Uriel Feige, Amos Korman, Yoav Rodeh.
    Searching Trees with Permanently Noisy Advice: Walking and Query Algorithms
    ACM Trans. Algorithms 2021.
    Version: January 2020.
  78. Uriel Feige.
    Introduction to Semi-Random Models.
    Chapter 9 in the book Beyond the Worst-Case Analysis of Algorithms, edited by Tim Roughgarden.
    Version: October 2019.
  79. Moshe Babaioff, Tomer Ezra, Uriel Feige.
    Fair and Truthful Mechanisms for Dichotomous Valuations.
    AAAI 2021.
    Version: July 2020.
  80. Uriel Feige, Vadim Grinberg.
    How to hide a clique?
    ICALP 2020.
    Version: April 2020.
  81. Uriel Feige, Amir Lellouche.
    Quantitative Group Testing and the rank of random matrices
    Version: June 2020.
  82. Moshe Babaioff, Tomer Ezra, Uriel Feige.
    Best-of-Both-Worlds Fair-Share Allocations.
    WINE 2022.
    Version: March 2022.
  83. Shahar Dobzinski, Uriel Feige, Michal Feldman.
    Are Gross Substitutes a Substitute for Submodular Valuations?
    EC 2021.
    Version: February 2022.
  84. Moshe Babaioff, Tomer Ezra, Uriel Feige.
    Fair-Share Allocations for Agents with Arbitrary Entitlement.
    EC 2021.
    Version: November 2021.
  85. Uriel Feige, Ariel Sapir, Laliv Tauber.
    A tight negative example for MMS fair allocations.
    WINE 2021.
    Version: April 2021.
  86. Uriel Feige, Tom Ferster.
    A tight bound for the clique query problem in two rounds.
    Version: December 2021.
  87. Uriel Feige.
    Maximin fair allocations with two item values.
    Version: February 2022.
  88. Uriel Feige, Yehonatan Tahan.
    On allocations that give intersecting groups their fair share.
    Version: April 2022.
  89. Uriel Feige, Alexey Norkin.
    Improved maximin fair allocation of indivisible items to three agents.
    Version: May 2022.
  90. Moshe Babaioff, Uriel Feige.
    Fair Shares: Feasibility, Domination and Incentives.
    EC 2022.
    Version: May 2022.
  91. Uriel Feige, Xin Huang.
    On picking sequences for chores.
    EC 2023.
    Version: November 2022.
  92. Gilad Ben Uziahu, Uriel Feige.
    On Fair Allocation of Indivisible Goods to Submodular Agents.
    COMSOC 2023 (poster).
    Version: March 2023.
  93. Uriel Feige.
    The inversion paradox, and classification of fairness notions.
    Version: November 2023.
  94. Uriel Feige.
    The Surprising Power of Spectral Refutation.
    Commun. ACM 68(3): 82 (2025)
  95. Moshe Babaioff, Uriel Feige.
    Share-Based Fairness for Arbitrary Entitlements.
    STOC 2025.
  96. Uriel Feige.
    Low communication protocols for fair allocation of indivisible goods.
    EC 2025
  97. Uriel Feige, Vadim Grinberg.
    Fair allocations with subadditive and XOS valuations.
    EC 2025
  98. Uriel Feige, Shengyu Huang.
    Concentration and maximin fair allocations for subadditive valuations.
    Version: February 2025.
  99. Uriel Feige.
    The residual maximin share.
    Version: June 2025.
  100. Uriel Feige.
    From multi-allocations to allocations, with subadditive valuations.
    Version: June 2025.