Finding the maximum number of disjoint spanning trees in a given graph is a well-studied problem with several applications and connections. The Tutte-Nash-Williams theorem provides a min-max relation for this problem which also extends to disjoint bases in a matroid and leads to efficient algorithms [Schrijver, 2003]. Several other packing problems such as element disjoint Steiner trees, disjoint set covers, and disjoint dominating sets are NP-Hard but admit an O(log n)-approximation [Feige et al., 2002; Cheriyan and Salavatipour, 2007]. Călinescu, Chekuri, and Vondrák [G. Călinescu et al., 2009] viewed all these packing problems as packing bases of a polymatroid and provided a unified perspective. Motivated by applications in wireless networks, recent works have studied the problem of packing set covers in the online model [Pananjady et al., 2015; Emek et al., 2019; Bienkowski et al., 2025]. The online model poses new challenges for packing problems. In particular, it is not clear how to pack a maximum number of disjoint spanning trees in a graph when edges arrive online. Motivated by these applications and theoretical considerations, we formulate an online model for packing bases of a polymatroid, and describe a randomized algorithm with a polylogarithmic competitive ratio. Our algorithm is based on interesting connections to the notion of quotients of a polymatroid that has recently seen applications in polymatroid sparsification [Quanrud, 2024]. We generalize the previously known result for the online disjoint set cover problem [Emek et al., 2019] and also address several other packing problems in a unified fashion. For the special case of packing disjoint spanning trees in a graph (or a hypergraph) whose edges arrive online, we provide an alternative to our general algorithm that is simpler and faster while achieving the same poly-logarithmic competitive ratio.

Blockchain-assisted federated learning (BFL) can achieve decentralized storage and management of model data without relying on a central server. However, security issues caused by deliberate attacks in distributed systems and efficiency issues induced by heterogeneous computing consumption in resource-limited systems need to be urgently addressed in BFL. To address these issues, we propose a decentralized reputation management (DRM) mechanism for a trustworthy BFL (T-BFL) network, that explores, stores, and utilizes the endogenous reputation of distributed nodes to promote system security and efficiency. The proposed DRM includes three core modules, i.e., decentralized reputation evaluation, reputation-based model aggregation, and reputation-based blockchain consensus. Specifically, in the off-chain phase of T-BFL, the reputation value of each node is evaluated based on model quality, which other peer nodes can verify. This reputation value further determines the weight of global aggregation at each node. In the on-chain phase, the reputation of each node serves as the stake to dynamically adjust its consensus difficulty. Furthermore, we investigate the convergence rate of the T-BFL network under the poisoning attack, and dynamically optimize the energy allocation of local training, consensus, and communications by minimizing the upper bound of the global loss function. Extensive experiments are conducted to evaluate the performance of T-BFL on MNIST, Fashion-MNIST, and Cifar-10 datasets. The experimental results demonstrate that, compared with traditional BFL, T-BFL can achieve up to 56.12% accuracy improvement and$8.6\times $acceleration for reaching the target learning accuracy under the poisoning attack.

Traditional federated learning (FL) frameworks rely on a central server for model coordination among distributed mobile terminals (MTs). The centralization faces two critical challenges, i.e., single point of failure and potential privacy leakage. Differentially private decentralized FL (DP-DFL) has been proposed to address these challenges, wherein the MTs exchange models in a decentralized manner and maintain the differential privacy (DP) guarantee by adding noise to local models before model interaction. However, existing DP-DFL frameworks confront difficulty in achieving the expected privacy and convergence performance, simultaneously. To address this issue, we propose a novel DP-DFL framework (called randomized DP-DFL) that employs a randomized model interaction scheme to lower the model exposure frequency and hence reduce privacy budget consumption. Specifically, the scheme includes two sequential steps, i.e., randomized terminal assignment and randomized model transmission. In Step 1), the model interaction phase of DFL is further divided into several sequential substages. MTs are randomly assigned to each sub-stage. In Step 2), each MT sequentially transmits either a model previously received from its neighbors or its own local model according to the assigned sub-stage order. The proposed scheme enhances the MTs' privacy of DFL since the exposure probabilities of the MTs' local models are significantly reduced via these two randomized steps. Besides, we theoretically analyze the convergence and privacy performance of randomized DP-DFL. In particular, properly tuning the number of sub-stages in randomized DP-DFL can achieve an optimal balance between privacy and convergence. Experimental results show that randomized DP-DFL consistently outperforms traditional frameworks. Compared with baselines, randomized DP-DFL reduces 40.9% privacy loss under the same target accuracy while improving 9.5% learning accuracy under the same privacy loss on EMNIST and CIFAR-10, respectively

In the Directed Steiner Tree (DST) problem the input is a directed edge-weighted graph G = (V,E), a root vertex r and a set S ⊆ V of k terminals. The goal is to find a min-cost subgraph that connects r to each of the terminals. DST admits an O(log² k/log log k)-approximation in quasi-polynomial time [Grandoni et al., 2022; Rohan Ghuge and Viswanath Nagarajan, 2022], and an O(k^{ε})-approximation for any fixed ε > 0 in polynomial-time [Alexander Zelikovsky, 1997; Moses Charikar et al., 1999]. Resolving the existence of a polynomial-time poly-logarithmic approximation is a major open problem in approximation algorithms. In a recent work, Friggstad and Mousavi [Zachary Friggstad and Ramin Mousavi, 2023] obtained a simple and elegant polynomial-time O(log k)-approximation for DST in planar digraphs via Thorup’s shortest path separator theorem [Thorup, 2004]. We build on their work and obtain several new results on DST and related problems. - We develop a tree embedding technique for rooted problems in planar digraphs via an interpretation of the recursion in [Zachary Friggstad and Ramin Mousavi, 2023]. Using this we obtain polynomial-time poly-logarithmic approximations for Group Steiner Tree [Naveen Garg et al., 2000], Covering Steiner Tree [Goran Konjevod et al., 2002] and the Polymatroid Steiner Tree [Gruia Călinescu and Alexander Zelikovsky, 2005] problems in planar digraphs. All these problems are hard to approximate to within a factor of Ω(log² n/log log n) even in trees [Eran Halperin and Robert Krauthgamer, 2003; Grandoni et al., 2022]. - We prove that the natural cut-based LP relaxation for DST has an integrality gap of O(log² k) in planar digraphs. This is in contrast to general graphs where the integrality gap of this LP is known to be Ω(√k) [Leonid Zosin and Samir Khuller, 2002] and Ω(n^{δ}) for some fixed δ > 0 [Shi Li and Bundit Laekhanukit, 2022]. - We combine the preceding results with density based arguments to obtain poly-logarithmic approximations for the multi-rooted versions of the problems in planar digraphs. For DST our result improves the O(R + log k) approximation of [Zachary Friggstad and Ramin Mousavi, 2023] when R = ω(log² k).

In the ELEMENT DISTINCTNESS problem, one is given an array a1,…, an of integers from [poly(n)] and is tasked to decide if {ai} are mutually distinct. Beame, Clifford and Machmouchi (FOCS 2013) gave a low-space algorithm for this problem that runs in space S(n) and time T(n) where T(n) ≤ Õ(n3/2/S(n)1/2), assuming a random oracle (i.e., random access to polynomially many random bits). A recent breakthrough by Chen, Jin, Williams and Wu (SODA 2022) showed how to remove the random oracle assumption in the regime S(n) = polylog(n) and T(n) = Õ(n3/2). They designed the first truly polylog(n)-space, Õ(n3/2)-time algorithm by constructing a small family of hash functions H ⊆ {h|h : [poly(n)] → [n]} with a certain pseudorandom property. In this paper, we give a significantly simplified analysis of the pseudorandom hash family by Chen et al. Our analysis clearly identifies the key pseudorandom property required to fool the BCM algorithm, allowing us to explore the full potential of this construction. Based on our new analysis, we show the following. • As our main result, we give a time-space tradeoff for ELEMENT DISTINCTNESS without random oracle. Namely, for every S(n),T(n) such that T ≈ Õ(n3/2/S(n)1/2), our algorithm can solve the problem in space S(n) and time T(n). Our algorithm also works for a related problem SET INTERSECTION, for which this tradeoff is tight due to a matching lower bound by Dinur (Eurocrypt 2020). • As a direct application of our technique, we show a more general pseudorandom property of the hash family, which we call the “c-connecting” property. It might be of independent interest. • The construction by Chen et al. needs O(log3 n log log n) random bits to sample the pseudorandom hash function. We slightly improve the seed length to O (log3 n). * The full version of the paper can be accessed at https://arxiv.org/abs/2210.07534