Giang T. Nguyen

Nigel Bean, Giang T. Nguyen, Federico Poloni

Fluid queues are mathematical models frequently used in stochastic modelling. Their stationary distributions involve a key matrix recording the conditional probabilities of returning to an initial level from above, often known in the literature as the matrix $Ψ$. Here, we present a probabilistic interpretation of the family of algorithms known as \emph{doubling}, which are currently the most effective algorithms for computing the return probability matrix $Ψ$. To this end, we first revisit the links described in \cite{ram99, soares02} between fluid queues and Quasi-Birth-Death processes; in particular, we give new probabilistic interpretations for these connections. We generalize this framework to give a probabilistic meaning for the initial step of doubling algorithms, and include also an interpretation for the iterative step of these algorithms. Our work is the first probabilistic interpretation available for doubling algorithms.

Juan A. Cabrera, Pit Hofmann, Jonas Schulz et al.

The Shared Prosperity Internet (SPI) is a network-computing architecture that makes the benefits of automation and Artificial Intelligence (AI) broadly accessible to the society. To ground its design, this paper maps the physical constraints of Shannon, Landauer, Turing, and Einstein to three design principles: trustworthiness, sustainability, and technological sovereignty, and maps them into three technical pillars: i) post-Shannon, goal-oriented communication that transmits only what the task requires; ii) anticipatory decision-making ("negative latency") with confidence-bounded pre-action and correction; and iii) beyond-digital computing that selects energy-optimal substrates under deadline and computability constraints. The SPI is grounded in three societal use cases: remote teaching for pupils, remote teaching of robots and cyber-physical systems, and elder care. Furthermore, this paper defines measurable outcomes for an SPI, including latency decomposition, bits per event, energy and CO2 per task, safety and privacy indicators, and robustness.

Peter Mathews, Caitlin Gray, Lewis Mitchell et al.

Tweet clustering for event detection is a powerful modern method to automate the real-time detection of events. In this work we present a new tweet clustering approach, using a probabilistic approach to incorporate temporal information. By analysing the distribution of time gaps between tweets we show that the gaps between pairs of related tweets exhibit exponential decay, whereas the gaps between unrelated tweets are approximately uniform. Guided by this insight, we use probabilistic arguments to estimate the likelihood that a pair of tweets are related, and build an improved clustering method. Our method Social Media Event Response Clustering (SMERC) creates clusters of tweets based on their tendency to be related to a single event. We evaluate our method at three levels: through traditional event prediction from tweet clustering, by measuring the improvement in quality of clusters created, and also comparing the clustering precision and recall with other methods. By applying SMERC to tweets collected during a number of sporting events, we demonstrate that incorporating temporal information leads to state of the art clustering performance.

Giang T. Nguyen, Federico Poloni

Markov-modulated fluid queues are popular stochastic processes frequently used for modelling real-life applications. An important performance measure to evaluate in these applications is their steady-state behaviour, which is determined by the stationary density. Computing it requires solving a (nonsymmetric) M-matrix algebraic Riccati equation, and indeed computing the stationary density is the most important application of this class of equations. Xue, Xu and Li [Numer. Math., 2012] provided a componentwise first-order perturbation analysis of this equation, proving that the solution can be computed to high relative accuracy even in the smallest entries, and suggested several algorithms for computing it. An important step in all proposed algorithms is using so-called triplet representations, which are special representations for M-matrices that allow for a high-accuracy variant of Gaussian elimination, the GTH-like algorithm. However, triplet representations for all the M-matrices needed in the algorithm were not found explicitly. This can lead to an accuracy loss that prevents the algorithms to converge in the componentwise sense. In this paper, we focus on the structured doubling algorithm, the most efficient among the proposed methods in Xue et al., and build upon their results, providing (i) explicit and cancellation-free expressions for the needed triplet representations, allowing the algorithm to be performed in a really cancellation-free fashion; (ii) an algorithm to evaluate the final part of the computation to obtain the stationary density; and (iii) a componentwise error analysis for the resulting algorithm, the first explicit one for this class of algorithms. We also present numerical results to illustrate the accuracy advantage of our method over standard (normwise-accurate) algorithms.