network protocol engineers

Abstract: We show positive and negative results on classical relay channels with entanglement assistance, revealing a sharp contrast between strictly causal and causal relay encoding. First, we consider van der Meulen's setting of a unit-delay relay, with strictly causal encoding. We show that the standard cutset upper bound continues to hold with entanglement assistance, and deduce that entanglement does not increase the capacity for several classes of relay channels. Second, we consider a zero-delay relay, where the encoding is causal. We present an example in which entanglement enables rates that exceed the cutset upper bound by at least 12.5%. Namely, entanglement shared between the source and relay significantly increases the capacity of a classical zero-delay relay channel.

Abstract: We derive an upper bound on the rate of a linear code capable of list decoding from insertion and deletion errors. Subsequently, we show that a linear code can list decode from at most $n - \frac{L}{L+1}k + 1$ insdel errors with fixed list size $L$, and that this bound is strict when the code does not contain the all-ones vector. We also provide a simple construction of codes achieving the optimal rate for any given list size capable of correcting a single insdel error. All the results hold for linear codes over finite fields of size $q \geq 3$.

Abstract: We provide a $\operatorname{poly}(\log\log n)$-round randomized LOCAL algorithm for the constructive Lovász Local Lemma with polynomial criterion $pd^{c} < 1$, for a sufficiently large constant $c$. The best previous general round complexity was $\widetilde O(\log n)$. The key ingredient is a local reduction that amplifies the LLL probability exponent quadratically, while increasing the dependency radius only by a constant factor.

Abstract: Many network protocols and distributed systems combine recursion, unbounded local state, and quantitative behaviour such as cost, latency, or reliability. Existing decidability results for networks of pushdown systems are largely qualitative, and do not extend to quantitative analyses, which must jointly track traces and weights. We present a framework for the quantitative verification of acyclic networks of weighted pushdown systems. Finitely summarising a recursive network component requires collapsing the infinite family of runs obtained by pumping its nested loops, and doing so \emph{exactly}, rather than by over-approximation, is a standing difficulty. We give a class of weight domains where this is possible: pumping semirings, those in which the weights accumulated by such a family collapse to a closed form; informally, the domain must be unable to count iterations. The class admits domains with infinite ascending chains, such as the arctic semiring and downward-closed languages. Over these, we give a terminating saturation algorithm computing quantitative reachability exactly, resting on two ideas: segment tree algebras, a compositional representation of runs, and thermal extensions, which symbolically separate accelerated weights so that further acceleration remains exact. We use this to compute upward and downward closures of context-free languages uniformly, and to lift the algorithm to acyclic networks over "thin" pumping semirings, yielding the first quantitative safety and reachability analyses for networks of pushdown systems.

Abstract: This work studies non-linear function computation broadcast (NFCB), in which a sender with access to $N$ datasets $(X_1,\dots,X_N)$ broadcasts a common message to $K$ users, each possessing side information and requesting a function of the datasets. The goal is to minimize the rate required for asymptotically lossless recovery of all demands. We introduce a broadcast graph that jointly captures the source distribution, side information, and demanded functions. Using Körner's characteristic-graph framework, we develop an achievable scheme for arbitrary $K$, general source distributions, and general finite-field demands, including linear, non-separable, and non-linear functions, without restricting the encoding or decoding operations to be linear. We also present a side-information-assisted independent-set scheme and characterize the optimal graph-based achievable rate for compatible functions. For the converse, we derive a multi-letter response-profile bound that strengthens a basic side-information converse, zero-error and asymptotically lossless clique-entropy bounds based on the operational block broadcast graph, and a genie-aided lower bound. For binary NFCB with $N=K$ and side information $X_i$ at user $i$, we characterize the optimal rate in several special cases and bound the worst-case and average additive gaps between the proposed achievable rate and the genie-aided converse for $K=3$ and $K=4$. Finally, three-user examples with Boolean and linear demands illustrate the proposed bounds and show that non-linear encoding can strictly outperform the best scalar and vector linear schemes.

Abstract: In this paper, we provide a single-letter characterization of the exact common information for a pair of correlated discrete sources, as well as a single-letter characterization of the admissible region for the shared randomness rate and the communication rate in exact channel synthesis.

Abstract: Decentralised federated learning replaces server aggregation with peer-to-peer model exchange, making collaborator selection a local decision under uncertainty. Fixed probe budgets waste effort on easy choices yet fall short when peers are hard to distinguish. We propose SAGE (Sequential Anchor-Gated Exchange), an optimal-stopping peer selector under a one-model-bearing-exchange budget. A receiver scores candidate neighbours on receiver-owned anchor evidence and selects once an advantage is certified. It continues probing only while further evidence repays its cost, and otherwise falls back to random gossip. We show that the stopping problem admits an optimal rule attained at a finite stage, and that the anchor schedule is order-optimal in the peer-risk gap and the confidence level. We further show that the selector never returns a peer worse than random gossip with high probability, and prove that no such guarantee holds for selectors that commit without a certificate. A separability threshold follows, below which no probing budget improves on gossip. Experiments span two image benchmarks, two graph families and three heterogeneity levels. Selectors that always act on their evidence lose to gossip in every configuration tested. SAGE-OS matches gossip on 75.5% less evidence than a fixed budget, at half the communication overhead of two published selectors. The operative decision is not which peer to rank first, but whether the evidence justifies ranking at all.

Abstract: The capacity of the relay channel is characterized by three schemes: decode-forward, coordinated compress-forward, and uncoordinated compress-forward. The proof relies entirely on properties of typical sequences.

Abstract: We study exploration of anonymous, port-free graphs by a single agent with no internal memory. To compensate for the lack of memory, the agent uses writable vertex colors as external memory. From every starting vertex, the agent must visit all vertices, return to its start, and terminate there. Throughout, recoloring is unrestricted, and the color count includes the common initial color. However, to our knowledge, no nontrivial color lower bound was known for unrestricted recoloring. We determine the optimal number of colors on two classes defined by block structure and prove the first nontrivial color lower bounds for unrestricted recoloring. First, a single three-color algorithm explores every tree and every simple cycle in $O(n)$ moves, and no algorithm with at most two colors explores $P_3$, the path on three vertices. Second, we give a four-color algorithm that explores every graph whose blocks are cycles or complete bipartite graphs in $O(n)$ moves, and we prove that no algorithm with at most three colors explores all subcubic pseudotrees. Hence four colors are optimal for every class between subcubic pseudotrees and this block-defined class. On cacti, this improves the previous five-color upper bound to a tight four. The lower bound reduces the possible initial actions by hand and rules out the remaining cases by a machine-checked SAT certificate on nine graphs with at most five vertices. Finally, we extend the known five-color algorithm for triangle-free graphs to graphs whose blocks are cliques or triangle-free, using $O(nΔ)$ moves, where $Δ$ is the maximum degree.

Abstract: The small-world phenomenon was given an algorithmic foundation by Kleinberg, who showed that in an augmented $k$-dimensional lattice a decentralized greedy algorithm delivers a message in $O(\log^2 n)$ expected steps. We study predicted-greedy routing, in which a mobile agent forwarding the message moves at each step to the neighbor minimizing a noisy $(\varepsilon,δ)$-prediction of its distance to the target, redrawn at every step from an oracle conditioned on the full routing history. Two cases arise from what this agent can observe. An agent with the coordinate awareness can still compute lattice distance exactly, but not graph distance in the shortcut-augmented network, since that depends on the shortcuts of nodes it has not yet visited; given an $(\varepsilon,δ)$-prediction of graph distance, information the classical model never supplies, it achieves expected delivery time $O(\log n/(1-4k\varepsilonδ))$, an asymptotic improvement over $Θ(\log^2 n)$. An agent with no coordinate awareness at all, the natural model for a privacy-preserving network whose nodes never disclose their coordinates, cannot compute even lattice distance; given an $(\varepsilon,δ)$-prediction of lattice distance instead, it still reaches the target in $O(n/(1-4k\varepsilonδ))$ expected steps. Together these results show that a modest amount of predicted information, of the right kind, is enough to accelerate decentralized routing well below Kleinberg's classical bound, and that even when nodes reveal no coordinates at all, reliable delivery remains achievable.