Papers for

distributed systems designers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Information distance cannot mimic lattices or Euclidean spaces exactly

Complete bipartite embeddings, lattice non-embeddability, and non-Euclidean powers of information distance

Abstract: We encode the vertices of every finite complete bipartite graph as binary strings at each scale. The information distances between these strings approximate the scaled graph distances with an additive error bounded by a constant independent of the scale. We also assign one fixed infinite binary sequence to each vertex; suitable prefixes satisfy the same distance estimate with logarithmic error. This extends Hutter's construction for $K_{3,3}$ and resolves his open problem on scale-embeddings of finite complete bipartite graphs. Combined with his complete bipartite obstruction, these embeddings show that no positive power of information distance can be represented exactly by distances in a real Hilbert space, resolving his question about such representations. For conditional prefix complexity, we further prove that at most $2^{δ+C}$ strings lie between any two strings with total distance exceeding their mutual distance by at most $δ$, where $C$ is independent of the endpoints. This bound rules out scale-embeddings of the integer line and every positive-dimensional integer lattice, resolving Hutter's lattice embedding problem for both string and sequence embeddings. Restriction to the integer lattice gives the same conclusion for $(\mathbb R^m,\|\cdot\|_1)$ for every $m\ge1$.

Wed 30 SeptInformation Theory
The gist
This paper studies how well certain ideas of measuring information similarity between data strings can represent distances in graphs and spaces. The authors solved an open problem by showing that no matter how you raise information distance to a positive power, you cannot perfectly capture distances in common geometric spaces like lattices or in Euclidean geometry. They also created new ways to encode special graphs with strings so that these approximate distances are consistent across different sizes. This work sets limits on how well information-based distances can mimic known structures.
Open → 2609.38919v1