ECCC-Report TR16-129https://eccc.weizmann.ac.il/report/2016/129Comments and Revisions published for TR16-129en-usWed, 24 May 2017 16:30:21 +0300
Revision 1
| Local Expanders |
Emanuele Viola,
Avi Wigderson
https://eccc.weizmann.ac.il/report/2016/129#revision1A 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}})$.Wed, 24 May 2017 16:30:21 +0300https://eccc.weizmann.ac.il/report/2016/129#revision1
Paper TR16-129
| Local Expanders |
Emanuele Viola,
Avi Wigderson
https://eccc.weizmann.ac.il/report/2016/129Abstract 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}})$.Tue, 16 Aug 2016 17:13:54 +0300https://eccc.weizmann.ac.il/report/2016/129