Explicit construction of efficient graphs improves program discovery and data access
Explicit unbalanced 1-expanders with small degree and right size
Computational ComplexityDiscrete Mathematics
Summary
The authors built a special type of network (called a 1-expander) that connects items on the left to items on the right with a small number of links. This network helps to quickly find short descriptions (or programs) that produce a given output, which is a key problem in understanding how complex data can be compressed and described. Their method speeds up an algorithm to list these short programs, making it more efficient than previous approaches. They also showed how this network can help create data structures that access memory predictably without changing during queries.
What this means in practice
- •For software engineers: Speed up algorithms that find short programs generating specific outputs by using efficient graph-based structures.
- •For database system developers: Design dynamic data dictionaries with predictable, fixed memory access patterns during queries using the new expander graphs.
Authors
Bruno Bauwens, Marius Zimand
Abstract
An explicit graph is given with left size $N$, left degree $\widetilde O(\log^2 N)$, right size $(1+o(1))K$ and $1$-expansion up to~$K$, meaning that every left subset of size $K' \le K$ has at least $K'$ 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 $\widetilde 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 $Ω(|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.