12 citations · 27 across the 12 of their papers we have counts for
Showing 2011 · cs.DSShow all
2 papers · 2 filters
cs.DS2011
Approximating Non-Uniform Sparsest Cut via Generalized Spectra
Venkatesan Guruswami, Ali Kemal Sinop
We give an approximation algorithm for non-uniform sparsest cut with the following guarantee: For any , given cost and demand graphs with edge weights respecti…
cs.DS2011
Optimal Column-Based Low-Rank Matrix Reconstruction
Venkatesan Guruswami, Ali Kemal Sinop
We prove that for any real-valued matrix , and positive integers , there is a subset of columns of such that projecting onto their span…