- 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. - 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. - Uriel Feige.

On Allocations that Maximize Fairness

SODA 2008, 287-293.

Version: October 2007. - 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. - 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. - 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. - 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. - Uriel Feige and Mohit Singh.

Edge coloring and decompositions of weighted graphs

Proceedings of ESA 2008: 405-416.

Version: June 2008. - 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. - Noga Alon and Uriel Feige.

On the power of two, three and four probes

Proceedings of SODA 2009, 346-354.

Version: December 2008. - 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. - 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. - 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. - 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. - 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. - 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. - Uriel Feige and Shimon Kogan.

Balanced coloring of bipartite graphs

Journal of Graph Theory, Volume 64, Number 4, pages 277-291.

Version: June 2009. - Reid Andersen and Uriel Feige.

Interchanging distance and capacity in probabilistic mappings

In arxiv.org.

Version: July 2009. - 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. - Uriel Feige and Ofer Zeitouni.

Deterministic approximation for the cover time of trees

In arxiv.org.

Version: September 2009. - Uriel Feige.

Faster FAST (Feedback Arc Set in Tournaments)

In arxiv.org.

Version: November 2009. - Uriel Feige.

On optimal strategies for a hat game on graphs

SIAM J. Discrete Math. 24(3): 782-791 (2010).

Version: April 2010. - Uriel Feige, Vahab Mirrokni, Jan Vondrak.

Maximizing non-monotone submodular functions

SIAM J. Comput. 40(4): 1133-1153 (2011).

Version: December 2009. - 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. - Uriel Feige and Dorit Ron.

Finding hidden cliques in linear time.

Proceedings of AOFA 2010.

Version: May 2010. - 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. - Uriel Feige and Shlomo Jozeph.

Oblivious Algorithms for the Maximum Directed Cut Problem.

In arxiv.org.

Version: October 2010. - 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]. - Uriel Feige and Moshe Tennenholtz.

Responsive lotteries.

Proceedings of SAGT 2010: 150-161.

Version: March 2011. - 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]. - Uriel Feige and Daniel Reichman.

Recoverable values for independent sets.

In arxiv.org. ICALP (1) 2011: 486-497.

Version: March 2011. - 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. - 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. - Yossi Azar, Uriel Feige, Michal Feldman, Moshe Tennenholtz.

Mastering multi-player games.

Proceedings of AAMAS 2012: 897-904. - Uriel Feige and Shlomo Jozeph.

Universal factor graphs.

In arxiv.org. ICALP (1) 2012: 339-350.

Version: April 2012. - Uriel Feige and Rani Izsak.

Welfare Maximization and the Supermodular Degree.

ITCS 2013: 247-256.

Version: February 2013. - 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. - Uriel Feige, Ron Lavi, Moshe Tennenholtz

Competition Among Asymmetric Sellers With Fixed Supply.

EC 2013: 415-416.

Version: May 2013. - Uriel Feige, Gil Kalai, Moshe Tennenholtz

The cascade auction - a mechanism for deterring collusion in auctions.

AAAI 2013.

Version: April 2013. - Amin Coja-Oghlan, Uriel Feige, Michael Krivelevich, Daniel Reichman

Contagious Sets in Expanders.

In arxiv.org.

Version: February 2014. Closely related to [54]. - Roee David, Uriel Feige

Connectivity of Random High Dimensional Geometric Graphs.

APPROX-RANDOM 2013: 497-512.

Version: June 2013. - Yossi Azar, Uriel Feige, Michal Feldman, Moshe Tennenholtz.

Sequential Decision Making with Vector Outcomes.

ITCS 2014: 195-206.

Version: December 2013. - Uriel Feige and Moshe Tennenholtz

Invitation Games and the Price of Stability.

ITCS 2014: 93-102.

Version: December 2013. - 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. - Uriel Feige

On robustly asymmetric graphs.

In arxiv.org.

Version: February 2014. - 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. - Uriel Feige and Shlomo Jozeph

Demand Queries with Preprocessing.

ICALP (1) 2014: 477-488.

Version: May 2014. - Uriel Feige

Why are images smooth?

ITCS 2015.

Version: June 2014. - 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]. - Uriel Feige, R. Ravi and Mohit Singh.

Short Tours through Large Linear Forests.

IPCO 2014: 273-284.

Version: April 2014. - Uriel Feige, Tomer Koren and Moshe Tennenholtz

Chasing Ghosts: Competing with Stateful Policies.

FOCS 2014. SICOMP 2017.

Version: February 2017. - 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. - Uriel Feige and Shlomo Jozeph

Separation between Estimation and Approximation.

ITCS 2015. ECCC report TR14-110.

Version: August 2014. - Uriel Feige, Michael Krivelevich and Daniel Reichman

Contagious Sets in Random Graphs

Annals of Applied Probability, 2017.

Version: July 2016. Closely related to [40]. - 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]. - Uriel Feige.

NP-hardness of hypercube 2-segmentation.

In arxiv.org.

Version: November 2014. - Uriel Feige, Yishay Mansour, Robert E. Schapire.

Learning and inference in the presence of corrupted inputs.

COLT 2015: 637-657.

Version: June 2015. - Uriel Feige and Moshe Tennenholtz.

Optimization with uniform size queries.

Algorithmica, 2017.

Version: May 2015. - Roee David and Uriel Feige.

On the effect of randomness on planted 3-coloring models

STOC 2016.

Version: March 2016. - 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. - Charles Bordenave, Uriel Feige, Elchanan Mossel.

Shotgun Assembly of Random Jigsaw Puzzles

Random Structures and Algorithms 2020.

Version: May 2016. - Uriel Feige, Michal Feldman, Inbal Talgam-Cohen.

Oblivious Rounding and the Integrality Gap.

Approx 2016.

Version: June 2016. - Uriel Feige and Tal Wagner.

Generalized Girth Problems in Graphs and Hypergraphs.

Submitted.

Version: July 2016. - Uriel Feige and Yael Hitron.

The ordered covering problem.

Algorithmica 2018.

Version: August 2017. - Uriel Feige, Michal Feldman, Inbal Talgam-Cohen.

Approximate Modularity Revisited.

STOC 2017, Sicomp 2020.

Version: March 2018. - Uriel Feige, Boaz Patt-Shamir, Shai Vardi.

On the Probe Complexity of Local Computation Algorithms.

ICALP 2018.

Version: March 2017. - 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. - Alon Eden, Uriel Feige, Michal Feldman

Max-Min Greedy Matching.

Approx 2019.

Version: March 2018. - 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. - Uriel Feige, Yishay Mansour, Robert E. Schapire.

Robust Inference for Multiclass Classification.

ALT 2018: 368-386.

Version: February 2018. - Uriel Feige, Janardhan Kulkarni, Shi Li.

A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time.

SODA 2019.

Version: July 2018. - Uriel Feige, David Gamarnik, Joe Neeman, Miklos Z. Racz, Prasad Tetali.

Finding cliques using few probes.

Random Structures and Algorithms, 2020.

Version: September 2018. - Uriel Feige.

A randomized strategy in the mirror game.

In arxiv.org.

Version: January 2019. - Moshe Babaioff, Uriel Feige.

A New Approach to Fair Distribution of Welfare.

WINE 2019.

Version: September 2019. - Uriel Feige, Shimon Kogan.

Target Set Selection for Conservative Populations.

Discret. Appl. Math 2021.

Version: September 2019. - Uriel Feige, Ella Fuchs.

On the path partition number of 6-regular graphs

Journal of Graph Theory 2022.

Version: November 2019. - 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. - 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. - Moshe Babaioff, Tomer Ezra, Uriel Feige.

Fair and Truthful Mechanisms for Dichotomous Valuations.

AAAI 2021.

Version: July 2020. - Uriel Feige, Vadim Grinberg.

How to hide a clique?

ICALP 2020.

Version: April 2020. - Uriel Feige, Amir Lellouche.

Quantitative Group Testing and the rank of random matrices

Version: June 2020. - Moshe Babaioff, Tomer Ezra, Uriel Feige.

Best-of-Both-Worlds Fair-Share Allocations.

WINE 2022.

Version: March 2022. - Shahar Dobzinski, Uriel Feige, Michal Feldman.

Are Gross Substitutes a Substitute for Submodular Valuations?

EC 2021.

Version: February 2022. - Moshe Babaioff, Tomer Ezra, Uriel Feige.

Fair-Share Allocations for Agents with Arbitrary Entitlement.

EC 2021.

Version: November 2021. - Uriel Feige, Ariel Sapir, Laliv Tauber.

A tight negative example for MMS fair allocations.

WINE 2021.

Version: April 2021. - Uriel Feige, Tom Ferster.

A tight bound for the clique query problem in two rounds.

Version: December 2021. - Uriel Feige.

Maximin fair allocations with two item values.

Version: February 2022. - Uriel Feige, Yehonatan Tahan.

On allocations that give intersecting groups their fair share.

Version: April 2022. - Uriel Feige, Alexey Norkin.

Improved maximin fair allocation of indivisible items to three agents.

Version: May 2022. - Moshe Babaioff, Uriel Feige.

Fair Shares: Feasibility, Domination and Incentives.

EC 2022.

Version: May 2022.