אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

Lossless vertex expanders are d-regular (or biregular) graphs in which every small set of vertices S has almost the largest possible number of neighbors d|S|. While random regular graphs are known to be lossless expanders with high probability, constructing them explicitly has been a longstanding challenge. 

In this talk, I will present the first explicit construction of constant-degree two-sided lossless vertex expanders. The resulting graphs also admit a free group action, and hence realize the new families of good quantum LDPC codes due to Lin and Hsieh. The construction is based on taking an appropriate product of a constant-sized lossless expander with a base graph constructed from LPS Ramanujan cubical complexes, which are natural high-dimensional generalizations of the well-known LPS Ramanujan graphs.

Based on joint work with Jun-Ting Hsieh, Alex Lubotzky, Sidhanth Mohanty and Rachel Zhang (FOCS 2025).