Revision #1 Authors: Emanuele Viola, Avi Wigderson

Accepted on: 24th May 2017 16:30

Downloads: 56

Keywords:

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.

TR16-129 Authors: Emanuele Viola, Avi Wigderson

Publication: 16th August 2016 17:13

Downloads: 632

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