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

This work studies super-Ramanujan graphs: \(d\)-regular graphs whose spectral expansion lies strictly below the Ramanujan threshold \(2\sqrt{d-1}\). Although this threshold is asymptotically optimal for fixed \(d\) as \(n\) tends to infinity, it leaves open the finer question of how small the spectral expansion can be as a joint function of ... more >>>