Expander Graphs are Non-Malleable Codes

Peter M. R. Rasmussen, Amit Sahai

Any $d$-regular graph on $n$ vertices with spectral expansion $\lambda$ satisfying $n=\Omega (d^3\log (d)/\lambda )$ yields a $O\left(\frac{{\lambda }^{3/2}}{d}\right)$-non-malleable code for single-bit mess…