## Deconstructing 1-local expanders

#### Webpage for a paper by Oded Goldreich

#### Abstract

Contemplating the recently announced 1-local expanders of
Viola and Wigderson (ECCC, TR16-129, 2016),
one may observe that weaker constructs are well know.
For example, 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)$.
Starting from a generic candidate for a 1-local expander,
we formulate a natural problem
regarding *coordinated random walks* (CRW)
on the corresponding *relocation* graph
(which has size that is logarithmic in the size of
the candidate 1-local graph), and observe that

- any solution to the CRW problem yields 1-local expanders,
and
- any constant-size expanding set of generators for
the symmetric group yields a solution to the CRW problem.

This yields an alternative construction and different analysis
than the one used by Viola and Wigderson.
Furthermore, we show that solving the CRW problem
is equivalent to constructing 1-local expanders.

#### Material available on-line

Back to
either Oded Goldreich's homepage
or general list of papers.