Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR16-152 | 17th April 2018 15:35

Deconstructing 1-local expanders

RSS-Feed




Revision #1
Authors: Oded Goldreich
Accepted on: 17th April 2018 15:35
Downloads: 586
Keywords: 


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.



Changes to previous version:

Fixing various minor errors and adding clarifications.


Paper:

TR16-152 | 27th September 2016 11:06

Deconstructing 1-local expanders





TR16-152
Authors: Oded Goldreich
Publication: 27th September 2016 11:06
Downloads: 1281
Keywords: 


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.



ISSN 1433-8092 | Imprint