## 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.