Fernando Granha Jeronimo: Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification

(Zoom password: 728726)

Expander graphs are fundamental objects in theoretical computer
science and mathematics. They have numerous applications in diverse
fields such as algorithm design, complexity theory, coding theory,
pseudorandomness, group theory, etc.

In this talk, we will describe an efficient algorithm that transforms
any bounded degree expander graph into another that achieves almost
optimal (namely, near-quadratic, $d \leq 1/\lambda^{2+o(1)}$)
trade-off between (any desired) spectral expansion $\lambda$ and
degree $d$. The optimal quadratic trade-off is known as the Ramanujan
bound, so our construction gives almost Ramanujan expanders from
arbitrary expanders.

This transformation preserves structural properties of the original
graph, and thus has many consequences. Applied to Cayley graphs, our
transformation shows that any expanding finite group has almost
Ramanujan expanding generators. Similarly, one can obtain almost
optimal explicit constructions of quantum expanders, dimension
expanders, monotone expanders, etc., from existing (suboptimal)
constructions of such objects.

Our results generalize Ta-Shma’s technique in his breakthrough paper
[STOC 2017], used to obtain explicit almost optimal binary
codes. Specifically, our spectral amplification extends Ta-Shma’s
analysis of bias amplification from scalars to matrices of arbitrary
dimension in a very natural way.

Joint work with: Tushant Mittal, Sourya Roy and Avi Wigderson