Local Expanders

by Emanuele Viola and Avi Wigderson

Oded's comments

I postponed posting this choice because I have been trying to understand it better. My deconstruction is posted HERE, and its summary follows. [Note (19/9/16): The foregoing notes have several inaccuracies (related to the effect of taking reverse steps during a random walk); see my revised text on deconstructing 1-local expanders.]

Contemplating the recently announced 1-local expanders of Viola and Wigderson, one may observe that weaker constructs that use logarithmic degree are well-known (e.g., the hypercube). Likewise, one may easily obtain a 4-regular $N$-vertex graph with spectral gap that is $\Omega(1/\log^2 N)$, and similarly a $O(1)$-regular $N$-vertex graph with spectral gap $1/\tildeO(\log N)$. Following this line of thought, we formulate a natural problem regarding ``coordinated random walks'' (CRW), and observe that (1) any solution to the CRW problem yields 1-local expanders, and (2) that any constant-size expanding set of generators for the symmetric group yields a solution to the CRW problem. This yields an arguably simpler construction and a more intuitive analysis than the one used by Viola and Wigderson. Lastly, a modest and natural generalization of the CRW problem is equivalent to the problem of constructing 1-local expanders.

The original abstract

Abstract A map $f:{0,1}^{n}\to {0,1}^{n}$ has locality t if every output bit of f depends only on t input bits. Arora, Steurer, and Wigderson (2009) ask if there exist bounded-degree expander graphs on $2^{n}$ nodes such that the neighbors of a node $x\in {0,1}^{n}$ can be computed by maps of constant locality.

We give an explicit construction of such graphs with locality one. We apply this construction to obtain lossless expanders with constant locality, and more efficient error reduction for randomized algorithms. We also give, for n of the form $n=3D4\cdot3^{t}$, an explicit construction of bipartite Ramanujan graphs of degree 3 with $2^{n}-1$ nodes in each side such that the neighbors of a node $x\in {0,1}^{n}\setminus\{0^{n}\}$ can be computed either (1) in constant locality or (2) in constant time using standard operations on words of length $\Omega(n)$.

Our results use in black-box fashion deep explicit constructions of Cayley expander graphs, by Kassabov (2007) for the symmetric group $S_{n}$ and by Morgenstern (1994) for the special linear group $SL(2,F_{2^{n}})$.

See ECCC TR16-129.

Back to list of Oded's choices.