A central challenge in network design is ensuring resilience: how can we guarantee multiple, independent, communication pathways between nodes, even when some connections fail in a network? In 1989, Zehavi and Itai formulated a graph-theoretic conjecture that captures the essence of this problem. They proposed that any \(k\)-vertex-connected graph contains \(k\) independent spanning trees rooted at any given root \(r\), which means that for every vertex \(v\) in the graph, the unique \(r-v\) paths within these \(k\) spanning trees are entirely disjoint, apart from their endpoints \(r\) and \(v\). Despite decades of effort, this conjecture has only been proven for \(k \le 4\) and for specific graph families using their underlying topological structure, leaving the general case as an open problem in graph theory with substantial consequences in the field of distributed algorithms.

An unbiased m-sparsification of a vector$p$E Rnis a random vector$Q$∊ Rnwith mean$p$that has at most m$n$nonzero coordinates. Unbiased sparsification compresses the original vector without introducing bias; it arises in various contexts, such as in federated learning and sampling sparse probability distributions. Ideally, unbiased sparsification should also minimize the expected value of a divergence function Div(Q, p) that measures how far away$Q$is from the original$p$. If$Q$is optimal in this sense, then we call it efficient. Our main results describe efficient unbiased sparsifications for divergences that are either permutation-invariant or additively separable. Surprisingly, the characterization for permutation-invariant divergences is robust to the choice of divergence function, in the sense that our class of optimal$Q$for squared Euclidean distance coincides with our class of optimal$Q$for Kullback-Leibler divergence, or indeed any of a wide variety of divergences.