Publications (35)
Oblivious Collaboration
Yehuda Afek, Yakov Babichenko, Uriel Feige +3
NP-hardness of hypercube 2-segmentation
Uriel Feige
On the diameter of the set of satisfying assignments in random satisfiable k-CNF formulas
Uriel Feige, Abraham D. Flaxman, Dan Vilenchik
A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium
Uriel Feige, Inbal Talgam-Cohen
Faster FAST(Feedback Arc Set in Tournaments)
Uriel Feige
On the Probe Complexity of Local Computation Algorithms
Uriel Feige, Boaz Patt-Shamir, Shai Vardi
Universal Factor Graphs
Uriel Feige, Shlomo Jozeph
Tighter bounds for online bipartite matching
Uriel Feige
Oblivious Algorithms for the Maximum Directed Cut Problem
Uriel Feige, Shlomo Jozeph
Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph
Aditya Bhaskara, Moses Charikar, Eden Chlamtac +2
Deterministic approximation for the cover time of trees
Uriel Feige, Ofer Zeitouni
Finding cliques using few probes
Uriel Feige, David Gamarnik, Joe Neeman +2
Recoverable Values for Independent Sets
Uriel Feige, Daniel Reichman
Approximate Modularity Revisited
Uriel Feige, Michal Feldman, Inbal Talgam-Cohen
A Unifying Hierarchy of Valuations with Complements and Substitutes
Uriel Feige, Michal Feldman, Nicole Immorlica +3
Contagious Sets in Expanders
Amin Coja-Oghlan, Uriel Feige, Michael Krivelevich +1
Why are images smooth?
Uriel Feige
Complete convergence of message passing algorithms for some satisfiability problems
Uriel Feige, Elchanan Mossel, Dan Vilenchik
Chasing Ghosts: Competing with Stateful Policies
Uriel Feige, Tomer Koren, Moshe Tennenholtz
On the Profile of Multiplicities of Complete Subgraphs
Uriel Feige, Anne Kenyon, Shimon Kogan
Random walks with the minimum degree local rule have $O(n^2)$ cover time
Roee David, Uriel Feige
Max-Min Greedy Matching
Alon Eden, Uriel Feige, Michal Feldman
Musical chairs
Yehuda Afek, Yakov Babichenko, Uriel Feige +3
Approximation thresholds for combinatorial optimization problems
Uriel Feige
Mechanism design with uncertain inputs (to err is human, to forgive divine)
Uriel Feige, Moshe Tennenholtz
Random 3CNF formulas elude the Lovasz theta function
Uriel Feige, Eran Ofek
A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time
Uriel Feige, Janardhan Kulkarni, Shi Li
Min-Max Graph Partitioning and Small Set Expansion
Nikhil Bansal, Uriel Feige, Robert Krauthgamer +5
Shotgun Assembly of Random Jigsaw Puzzles
Charles Bordenave, Uriel Feige, Elchanan Mossel
On giant components and treewidth in the layers model
Uriel Feige, Jonathan Hermon, Daniel Reichman
Contagious Sets in Random Graphs
Uriel Feige, Michael Krivelevich, Daniel Reichman
On robustly asymmetric graphs
Uriel Feige
Interchanging distance and capacity in probabilistic mappings
Reid Andersen, Uriel Feige
On the effect of randomness on planted 3-coloring models
Roee David, Uriel Feige
A randomized strategy in the mirror game
Uriel Feige