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}})$.
Added an application to hardness amplification of one-way permutations, and also made other small changes.
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}})$.
