Showing cs.DSShow all
2 papers · 1 filter
cs.DS2018
Spectrally Robust Graph Isomorphism
Alexandra Kolla, Ioannis Koutis, Vivek Madan +1
We initiate the study of spectral generalizations of the graph isomorphism problem. (a)The Spectral Graph Dominance (SGD) problem: On input of two graphs and does there exi…
cs.DS2013
Towards a better approximation for sparsest cut?
Sanjeev Arora, Rong Ge, Ali Kemal Sinop
We give a new -approximation for sparsest cut problem on graphs where small sets expand significantly more than the sparsest cut (sets of size expand by a factor $\sqr…