Optimal Small Set Expanders and Their Codes
Provides theoretical foundations for optimal expanders, which are relevant for coding theory and cryptography, though the results are primarily combinatorial and the cryptographic application is discussed rather than demonstrated.
The paper characterizes optimal small-set expanders via girth and proves their existence for every expansion parameter. It also shows that optimality yields new lower bounds on neighbor counts for larger sets, with applications to post-quantum cryptography codes.
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.