Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Revision(s):

Revision #1 to TR16-129 | 24th May 2017 16:30

Local Expanders

Revision #1
Authors: Emanuele Viola, Avi Wigderson
Accepted on: 24th May 2017 16:30
Downloads: 56
Keywords:

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 then give three applications of this construction: (1) lossless
expanders with constant locality, (2) more efficient error reduction for
randomized algorithms, and (3) more efficient hardness amplification of
one-way permutations.

We also give, for n of the form $n=4\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}})$.

Changes to previous version:

Added an application to hardness amplification of one-way permutations, and also made other small changes.

Paper:

TR16-129 | 16th August 2016 17:13

Local Expanders

TR16-129
Authors: Emanuele Viola, Avi Wigderson
Publication: 16th August 2016 17:13
Downloads: 632
Keywords:

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=4\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}})$.

ISSN 1433-8092 | Imprint