#### Theory Seminar

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

This event is free and open to the publicAdd to Google Calendar

(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