10 citations · 16 across the 3 of their papers we have counts for
5 papers
Deterministic approximation for the cover time of trees
Uriel Feige, Ofer Zeitouni
We present a deterministic algorithm that given a tree T with n vertices, a starting vertex v and a slackness parameter epsilon > 0, estimates within an additive error of epsilon t…
Interchanging distance and capacity in probabilistic mappings
Reid Andersen, Uriel Feige
Harald Racke [STOC 2008] described a new method to obtain hierarchical decompositions of networks in a way that minimizes the congestion. Racke's approach is based on an equivalenc…
On the diameter of the set of satisfying assignments in random satisfiable k-CNF formulas
Uriel Feige, Abraham D. Flaxman, Dan Vilenchik
It is known that random k-CNF formulas have a so-called satisfiability threshold at a density (namely, clause-variable ratio) of roughly 2^k\ln 2: at densities slightly below this…
Random 3CNF formulas elude the Lovasz theta function
Uriel Feige, Eran Ofek
Let be a 3CNF formula with n variables and m clauses. A simple nonconstructive argument shows that when m is sufficiently large compared to n, most 3CNF formulas are not satisf…
Approximation thresholds for combinatorial optimization problems
Uriel Feige
An NP-hard combinatorial optimization problem is said to have an {\em approximation threshold} if there is some such that the optimal value of can be approximated in po…