14 citations · 56 across the 7 of their papers we have counts for
Showing cs.DSShow all
2 papers · 1 filter
cs.DS2013★ 14 cited
Sparsest Cut on Bounded Treewidth Graphs: Algorithms and Hardness Results
Anupam Gupta, Kunal Talwar, David Witmer
We give a 2-approximation algorithm for Non-Uniform Sparsest Cut that runs in time , where is the treewidth of the graph. This improves on the previous -appr…
cs.DS2012★ 3 cited
Markov chain methods for small-set expansion
Ryan O'Donnell, David Witmer
Consider a finite irreducible Markov chain with invariant distribution . We use the inner product induced by and the associated heat operator to simplify and generalize some…