标题： 显式无损顶点扩张器 显示英文标题

标题： Explicit Lossless Vertex Expanders

摘要： 我们给出了显式常度无损顶点扩展器的第一个构造。 具体而言，对于任何$\varepsilon > 0$和足够大的$d$，我们给出了一个无限族$d$-正则图的显式构造，其中每个小集合$S$的顶点有$(1-\varepsilon)d|S|$个邻居 （这意味着$(1-2\varepsilon)d|S|$个唯一邻居）。 我们的结果还可以自然地扩展为构造任意常数不平衡的双正则二部图，其中每一侧的小集合都有强扩展保证。 我们构造的图具有自由群作用，因此实现了 Lin 和 M. Hsieh 的新型量子 LDPC 码，并具有线性时间解码算法。 我们的构造基于将一个固定大小的无损扩展器与从 Ramanujan Cayley 立方复形构造的基图进行适当乘积。 显示英文摘要

摘要： We give the first construction of explicit constant-degree lossless vertex expanders. Specifically, for any $\varepsilon > 0$ and sufficiently large $d$, we give an explicit construction of an infinite family of $d$-regular graphs where every small set $S$ of vertices has $(1-\varepsilon)d|S|$ neighbors (which implies $(1-2\varepsilon)d|S|$ unique-neighbors). Our results also extend naturally to construct biregular bipartite graphs of any constant imbalance, where small sets on each side have strong expansion guarantees. The graphs we construct admit a free group action, and hence realize new families of quantum LDPC codes of Lin and M. Hsieh with a linear time decoding algorithm. Our construction is based on taking an appropriate product of a constant-sized lossless expander with a base graph constructed from Ramanujan Cayley cubical complexes.