We study the problem of detecting and recovering a planted spanning tree $M_n^*$ hidden within a complete, randomly weighted graph $G_n$. Specifically, each edge $e$ has a non-negative weight drawn independently from $P_n$ if $e \in M_n^*$ and from $Q_n$ otherwise, where $P_n \equiv P$ is fixed and $Q_n$ scales with $n$ such that its density at the origin satisfies $\lim_{n\to\infty} n Q’_n(0)=1.$ We consider two representative cases: when $M_n^*$ is either a uniform spanning tree or a uniform Hamiltonian path. We analyze the recovery performance of the minimum spanning tree (MST) algorithm and derive a fixed-point equation that characterizes the asymptotic fraction of edges in $M_n^*$ successfully recovered by the MST as $n \to \infty.$ Furthermore, we establish the asymptotic mean weight of the MST, extending Frieze’s $\zeta(3)$ result to the planted model. {Leveraging this result, we design an efficient test based on the MST weight and show that it can distinguish the planted model from the unplanted model with vanishing testing error as $n \to \infty.$} Our analysis relies on an asymptotic characterization of the local structure of the planted model, employing the framework of local weak convergence.

We consider a setting in which the agent aims to maximize the expected cumulative reward, subject to a constraint that the entropic risk of the total utility exceeds a given threshold. Unlike the risk-neutral case, standard primal-dual approaches fail to directly yield regret and violation bounds, as value iteration with respect to a combined state-action value function is not applicable in the risk-sensitive setting. To address this, we adopt the Optimized Certainty Equivalent (OCE) representation of the entropic risk measure and reformulate the problem by augmenting the state space with a continuous budget variable. We then propose a primal-dual algorithm tailored to this augmented formulation. In contrast to the standard approach for risk-neutral CMDPs, our method incorporates a truncated dual update to account for the possible absence of strong duality. We show that the proposed algorithm achieves regret of $\tilde{\mathcal{O}}\big(V_{g,\max}K^{3/4} + \sqrt{H^4 S^2 A \log(1/\delta)}K^{3/4}\big)$ and constraint violation of $\tilde{\mathcal{O}}\big(V_{g,\max} \sqrt{ {H^3 S^2 A \log(1/\delta)}}K^{3/4} \big)$ with probability at least $1-\delta$, where $S$ and $A$ denote the cardinalities of the state and action spaces, respectively, $H$ is the episode length, $K$ is the number of episodes, $\alpha < 0$ is the risk-aversion parameter, and $V_{g,\max} = \frac{1}{|\alpha|}(\exp(|\alpha|H) - 1)$. To the best of our knowledge, this is the first result establishing sublinear regret and violation bounds for the risk-sensitive CMDP problem.

Predicting the edge weights of a graph is a critical task across many domains. Some examples include predicting traffic flow in transportation networks, strength of interactions in protein-protein networks, and collaboration frequency in co-authorship networks. Graph Neural Networks have been very successful in edge-weight prediction tasks. However, these predictions lack rigorous statistical uncertainty quantification. Recent work has demonstrated the efficacy of conformal inference in quantifying the uncertainties of the predictions made by graph neural networks. However, there has been limited research in conformal inference for edge-weight prediction.

Recent studies suggested that the BitTorrent’s rarest-first (RF) protocol, owing to its work-conserving nature, can become unstable in the presence of non-persistent users. Consequently, for any provably stable protocol, many peers, at some point, have to be forced to hold off their file-download activity. In this work, we propose a tunable piece-selection policy that minimizes this (undesirable) requisite by combining the (work-conserving but not stabilizing) RF protocol with only an appropriate share of the (stabilizing but not work-conserving) mode-suppression (MS) protocol. We refer to this policy as “Rarest-First with Probabilistic Mode-Suppression” or simply RFwPMS. We study RFwPMS using a stochastic abstraction of the BitTorrent network that is general enough to capture a multi-swarm setting of non-persistent users—each swarm having its own altruistic preferences that may or may not overlap with those of other swarms. Using Lyapunov drift analysis, we show that for all kinds of inter-swarm behaviors and all arrival-rate configurations, RFwPMS is stable. Then, using the Kingman’s moment bound technique, we further show that the steady-state expected sojourn time of RFwPMS is independent of the arrival-rate in the single-swarm case (under a mild additional assumption). Finally, our simulation-based performance evaluation confirms our theoretical findings, and shows that the steady-state expected sojourn time is linear in the file-size (compared to our loose estimate of a polynomial with degree 6). Overall, an improved performance is observed in comparison to previously proposed stabilizing schemes like MS.

Many policy-based reinforcement learning (RL) algorithms can be viewed as instantiations of approximate policy iteration (PI), i.e., where policy improvement and policy evaluation are both performed approximately. In applications where the average reward objective is the meaningful performance metric, often discounted reward formulations are used with the discount factor being close to $1,$ which is equivalent to making the expected horizon very large. However, the corresponding theoretical bounds for error performance scale with the square of the horizon. Thus, even after dividing the total reward by the length of the horizon, the corresponding performance bounds for average reward problems go to infinity. Therefore, an open problem has been to obtain meaningful performance bounds for approximate PI and RL algorithms for the average-reward setting. In this paper, we solve this open problem by obtaining the first non-trivial finite time error bounds for average-reward MDPs which go to zero in the limit as policy evaluation and policy improvement errors go to zero.

Recent studies have suggested that the BitTorrent's rarest-first protocol, owing to its work-conserving nature, can become unstable in the presence of non-persistent users. Consequently, in any stable protocol, many peers are at some point endogenously forced to hold off their file-download activity. In this work, we propose a tunable piece-selection policy that minimizes this (undesirable) requisite by combining the (work-conserving) rarest-first protocol with only an appropriate share of the (non-work conserving) mode-suppression protocol. We refer to this policy as "Rarest-First with Probabilistic Mode-Suppression" or simply RFwPMS. We study RFwPMS under a stochastic model of the BitTorrent network that is general enough to capture multiple swarms of non-persistent users - each swarm having its own altruistic preferences that may or may not overlap with those of other swarms. Using a Lyapunov drift analysis, we show that RFwPMS is provably stable for all kinds of inter-swarm behaviors, and that the use of rarest-first instead of random-selection is indeed more justified. Our numerical results suggest that RFwPMS is scalable in the general multi-swarm setting and offers better performance than the existing stabilizing schemes like mode-suppression.

In this paper, we formulate an integer linear programming (ILP) to perform multicast routing and spectrum assignment (MRSA) in elastic optical networks, which serves jointly a set of multicast requests. In this formulation, all physical layer restrictions including modulation level assignment, maximum number of multicast capable nodes (MCNs), and maximum splitting degree (MSD) of MCNs, are considered. In addition, we modify the proposed joint ILP to serve multicast requests one-by-one, which is referred to as a separate ILP. Furthermore, we present three heuristic algorithms for MRSA, namely distance-based MRSA (DMRSA), congestion-based MRSA (CMRSA), and mixed CMRSA/DMRSA, which are applicable in both static and dynamic operation scenarios. In CMRSA and DMRSA, the link length and the amount of occupied spectrum are considered as the cost function of multicast routing, respectively; and in mixed CMRSA/DMRSA, a combination of normalized link length and normalized occupied spectrum is considered as the cost function. The comparison of ILPs and heuristic algorithms in static operation reveals that the joint ILP, as the benchmark, gives the optimum solution while has the most computational complexity. Furthermore, the separate ILP has lower complexity at the cost of consuming slightly more spectrum. Unless the DMRSA method, which has the worst performance, the gap between the other two heuristic algorithms and the ILPs is negligible. Furthermore, simulation results of dynamic operation scenarios reveal that mixed CMRSA/DMRSA outperforms other two heuristics algorithms in terms of blocking probability.

The threshold model is widely used to study the propagation of opinions and technologies in social networks. In this model individuals adopt the new behavior based on how many neighbors have already chosen it. We study cascades under the threshold model on sparse random graphs with community structure to see whether the existence of communities affects the number of individuals who finally adopt the new behavior. Specifically, we consider the permanent adoption model where nodes that have adopted the new behavior cannot change their state. When seeding a small number of agents with the new behavior, the community structure has little effect on the final proportion of people that adopt it, i.e., the contagion threshold is the same as if there were just one community. On the other hand, seeding a fraction of population with the new behavior has a significant impact on the cascade with the optimal seeding strategy depending on how strongly the communities are connected. In particular, when the communities are strongly connected, seeding in one community outperforms the symmetric seeding strategy that seeds equally in all communities.

In this study, the authors explore a generalised scheme for the synchronous code division multiple access (CDMA). In this scheme, unlike the standard CDMA systems, each user has different codewords for communicating different messages. Two main problems are investigated. The first problem concerns whether uniquely detectable overloaded matrices (an injective matrix, i.e. the inputs and outputs are in one‐to‐one correspondence depending on the input alphabets) exist in the absence of additive noise, and if so, whether there are any practical optimum detectors for such input codewords. The second problem is about finding tight bounds for the sum channel capacity. In response to the first problem, the authors have constructed uniquely detectable matrices for the generalised scheme and the authors have developed practical maximum likelihood detection algorithms for such codes. In response to the second problem, lower bounds and conjectured upper bounds are derived. The results of this study are superior to other standard overloaded CDMA codes since the generalisation can support more users than the previous schemes.