Optimal Small Set Expanders and Their Codes
2026-06-22 • Cryptography and Security
Cryptography and SecurityInformation Theory
AI summaryⓘ
The authors study a special type of bipartite graph where each vertex on one side connects to a fixed number of vertices on the other side. They focus on how well small groups of these vertices expand by having many neighbors, defining what it means to be 'optimal' in this context. The paper characterizes these optimal expanders using a graph property called girth and proves that such optimal graphs exist for any size parameter. They also show that these optimal graphs give stronger guarantees for larger groups. Finally, the authors explain how these graphs can help design better codes for secure communication in future quantum-resistant cryptography.
bipartite graphleft-regular graphsmall-set expanderneighborsgirthgraph expansionpost-quantum cryptographykey exchangeerror-correcting codesoptimal expander
Authors
Tristram Bogart, Marcelo Fiori, Pedro Raigorodsky, Mauricio Velasco
Abstract
A left-regular bipartite graph $G$ of degree $d$ is called a $(t,α)$-small-set-expander if every subset $X$ of left vertices of size at most $t$ has at least $α|X|$ neighbors. Such a graph is an optimal small-set expander if small subsets have as many neighbors as possible. We characterize optimal expanders combinatorially via girth and prove the existence of $s$-optimal expanders for every $s$. We also prove that $s$-optimality yields new "transfer" lower bounds on the number of neighbors of sets of size $h\geq s$. Finally, as an application, we discuss the use of optimal small-set expanders in building good codes for key exchange protocols in post-quantum cryptography.