[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, to appear.
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).
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
Accepted to Random Structures and Algorithms.
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.
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.
Submitted.
Version: September 2019.
[76] Uriel Feige, Ella Fuchs.
On the path partition number of 6-regular graphs
Submitted.
Version: November 2019.
[77] Lucas Boczkowski, Uriel Feige, Amos Korman, Yoav Rodeh.
Searching Trees with Permanently Noisy Advice: Walking and Query Algorithms
Submitted.
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.
Submitted.
Version: March 2021.
[83] Shahar Dobzinski, Uriel Feige, Michal Feldman.
Are Gross Substitutes a Substitute for Submodular Valuations?
EC 2021.
Version: February 2021.
[84] Moshe Babaioff, Tomer Ezra, Uriel Feige.
Fair-Share Allocations for Agents with Arbitrary Entitlement.
EC 2021.
Version: June 2021.
[85] Uriel Feige, Ariel Sapir, Laliv Tauber.
A tight negative example for MMS fair allocations.
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.
Version: May 2022.