14 citations · 32 across the 5 of their papers we have counts for
Showing math.PRShow all
2 papers · 1 filter
math.PR2009
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…
math.PR2008★ 14 cited
A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks
Omer Angel, Abraham D. Flaxman, David B. Wilson
In the complete graph on n vertices, when each edge has a weight which is an exponential random variable, Frieze proved that the minimum spanning tree has weight tending to zeta(3)…