Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Ramanujan:
TR16-129 | 16th August 2016
Emanuele Viola, Avi Wigderson

Local Expanders

Revisions: 1

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 ... more >>>

ISSN 1433-8092 | Imprint