2025/12/10 by Ali Khalesi, Khalesi, Ali, Mohammad Reza Deylam Salehi +1
Computer Science · #Graph Theory and Algorithms #Distributed and Parallel Computing Systems #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.2512.09858
We solve, in the typical-case sense, the multi-sender linearly-decomposable distributed computing problem introduced by tessellated distributed computing. We model real-valued encoders/decoders and demand matrices, and assess structural fidelity via a thresholded graph edit distance between the demand support and the two-hop support of the computed product. Our analysis yields: a closed-form second-moment (Frobenius) risk under spike-and-slab ensembles; deterministic links between thresholded GED and norm error; a Gaussian surrogate with sub-exponential tails that exposes explicit recall lines; concentration of GED and operator-norm control; and a compute-capped design with a visible knee. We map the rules to aeronautical and satellite networks.