Show simple item record

dc.contributor.authorAllen-Zhu, Zeyuanen_US
dc.contributor.authorBhaskara, Adityaen_US
dc.contributor.authorLattanzi, Silvioen_US
dc.contributor.authorMirrokni, Vahaben_US
dc.contributor.authorOrecchia, Lorenzoen_US
dc.coverage.spatialSociety for Industrial and Applied Mathematicsen_US
dc.date.accessioned2019-12-19T14:45:07Z
dc.date.available2019-12-19T14:45:07Z
dc.date.issued2016
dc.identifier.citationZeyuan Allen-Zhu, Aditya Bhaskara, Silvio Lattanzi, Vahab Mirrokni, Lorenzo Orecchia. 2016. "Expanders via local edge flips." Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, https://doi.org/10.1137/1.9781611974331.ch19
dc.identifier.urihttps://hdl.handle.net/2144/39014
dc.description.abstractDesigning distributed and scalable algorithms to improve network connectivity is a central topic in peer-to-peer networks. In this paper we focus on the following well-known problem: given an n-node d-regular network for d = Ω(log n), we want to design a decentralized, local algorithm that transforms the graph into one that has good connectivity properties (low diameter, expansion, etc.) without affecting the sparsity of the graph. To this end, Mahlmann and Schindelhauer introduced the random “flip” transformation, where in each time step, a random pair of vertices that have an edge decide to ‘swap a neighbor’. They conjectured that performing O(nd) such flips at random would convert any connected d-regular graph into a d-regular expander graph, with high probability. However, the best known upper bound for the number of steps is roughly O(n17d23), obtained via a delicate Markov chain comparison argument. Our main result is to prove that a natural instantiation of the random flip produces an expander in at most steps, with high probability. Our argument uses a potential-function analysis based on the matrix exponential, together with the recent beautiful results on the higher-order Cheeger inequality of graphs. We also show that our technique can be used to analyze another well-studied random process known as the ‘random switch’, and show that it produces an expander in O(nd) steps with high probability.en_US
dc.format.extentp. 259 - 269en_US
dc.language.isoen_US
dc.publisherSIAMen_US
dc.relation.ispartofProceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms
dc.subjectData structures and algorithmsen_US
dc.titleExpanders via local edge flipsen_US
dc.typeConference materialsen_US
dc.identifier.doi10.1137/1.9781611974331.ch19
pubs.elements-sourcemanual-entryen_US
pubs.notesEmbargo: Not knownen_US
pubs.organisational-groupBoston Universityen_US
pubs.organisational-groupBoston University, College of Arts & Sciencesen_US
pubs.organisational-groupBoston University, College of Arts & Sciences, Department of Computer Scienceen_US
pubs.publication-statusPublisheden_US
dc.identifier.mycv72593


This item appears in the following Collection(s)

Show simple item record