3 papers
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…
cs.LG2008
Isotropic PCA and Affine-Invariant Clustering
S. Charles Brubaker, Santosh S. Vempala
We present a new algorithm for clustering points in R^n. The key property of the algorithm is that it is affine-invariant, i.e., it produces the same partition for any affine trans…
cs.DS2006
Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting
Daniel Stefankovic, Santosh Vempala, Eric Vigoda
We present a near-optimal reduction from approximately counting the cardinality of a discrete set to approximately sampling elements of the set. An important application of our wor…