Optimal Small Set Expanders and Their Codes

Abstract

A left-regular bipartite graph $G$ of degree $d$ is called a $(t,\hat{I}\pm )$-small-set-expander if every subset $X$ of left vertices of size at most $t$ has at least $\hat{I}\pm |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\ge 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.

19 pages, 1 figure