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. Moshe Babaioff, Uriel Feige.
    Share-Based Fairness for Arbitrary Entitlements.
    Version: May 2024.
  95. Uriel Feige.
    Low communication protocols for fair allocation of indivisible goods.
    Version: July 2024.