Explicit unbalanced 1-expanders with small degree and right size

Abstract

An explicit graph is given with left size $N$, left degree $\tilde{O}({\log }^{2}N)$, right size $(1+o(1))K$ and $1$-expansion up to~$K$, meaning that every left subset of size $K^{\prime }\le K$ has at least $K^{\prime }$ neighbors. Let $\C(x)$ be the minimal length of a program that prints~$x$ (i.e., the central concept in Kolmogorov complexity). The $1$-expander is used to obtain an algorithm that on input $x$ computes in time $\poly(|x|)$ a list with $\tilde{O}(|x{|}^3)$ programs such that at least 1 program prints $x$ and has length $\C(x) + O(1)$. This improves on the $O(|x|^{6+\eps})$ upper bound in~\cite{zim:c:shortlistshortproof} and is close to the $\Omega (|x{|}^2)$ lower bound from~\cite[theorem 4]{bmvz:j:shortlist}. In the companion paper ``Online matching games in bipartite expanders: applications to data structures," the $1$-expander is used to obtain dynamic dictionaries in which the query operation has non-adaptive memory access.