518 citations · 948 across the 34 of their papers we have counts for
Showing cs.DMShow all
2 papers · 1 filter
cs.DM2010
Satisfiability Thresholds for k-CNF Formula with Bounded Variable Intersections
Karthekeyan Chandrasekaran, Navin Goyal, Bernhard Haeupler
We determine the thresholds for the number of variables, number of clauses, number of clause intersection pairs and the maximum clause degree of a k-CNF formula that guarantees sat…
cs.DM2008
Expanders via Random Spanning Trees
Navin Goyal, Luis Rademacher, Santosh Vempala
Motivated by the problem of routing reliably and scalably in a graph, we introduce the notion of a splicer, the union of spanning trees of a graph. We prove that for any bounded-de…