# Expander via Local Edge Flips

### Venue

SODA (2016)

### Publication Year

2016

### Authors

Zeyuan Allen-Zhu, Aditya Bhaskara, Silvio Lattanzi, Vahab Mirrokni, Lorenzo Orecchia

### BibTeX

## Abstract

Designing 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 O(n2d2[EQUATION] n) 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.