network engineers

Abstract: Network Digital Twins (NDTs) are important enablers of 6G and future networks. However, there is a lack of studies regarding practical aspects, such as the impact of simultaneously changing twinning rate, fidelity, and other NDT operational parameters. For instance, works often consider the impact of operational parameters in isolation or with physical twin (PTwin) implementations relying on simulations. Therefore, the main contribution of this work is to provide an in-depth study on the performance impacts of both twinning rate and fidelity, using PTwins that rely on measurements obtained from hardware. We also investigate the optimization of these two operational parameters to minimize energy consumption, exploring a Bayesian Optimization (BO) method and what-if analysis. In this work, the NDT models an indoor propagation environment to optimize beam management. The virtual twin (VTwin) was implemented with the Sionna ray tracing (RT) simulator and the PTwin with our in-house setup composed of customized Wi-Fi radios with 32 antenna elements operating at 60 GHz. The study reveals important aspects of wireless channel NDTs, suggesting that fidelity levels vary throughout the experiment and with the what-if difficulty. Moreover, the twinning rate can be adjusted using sample-efficient methods, such as BO, even at lower fidelity levels.

Abstract: Let $λ_k(G)$ be the $k$th eigenvalue of the normalized Laplacian of a finite undirected weighted graph, and let $ρ_G(k)$ be the minimum possible maximum conductance of $k$ disjoint nonempty vertex sets. We prove \[ ρ_G(k)\le C[1+\log(k+1)]^5\sqrt{λ_k(G)} \] for an absolute constant $C$. The construction gives exactly $k$ sets and a bound in terms of $λ_k(G)$, with all boundaries and volumes measured in the original graph. More strongly, it yields $k$ nonnegative functions with pairwise disjoint supports and Rayleigh quotients $O([1+\log(k+1)]^{10}λ_k(G))$. The proof uses independent local cutoffs whose lost covariance is controlled by conditioning on the loss along a principal direction in each cell. A regularized spectral embedding bounds cutoff energy on the entire original low eigenspace, while an adaptive construction reduces the remaining coefficient dimension by at least half at each stage. A dimension argument then converts almost rank-one local covariances into exactly $k$ scalar witnesses.

Abstract: The ongoing transition toward quantum-safe networking has motivated the development of hybrid network architectures integrating Quantum Key Distribution (QKD) and Post-Quantum Cryptography (PQC). However, the experimental evaluation of hybrid QKD-PQC network architectures remains constrained by the high cost and limited accessibility of quantum hardware, as well as by the limited support for hybrid QKD-PQC networks in existing emulation platforms. Quditto is an open-source emulation platform originally designed for QKD networks that enables cost-effective and reproducible experimentation without requiring dedicated physical quantum infrastructure. Building on this foundation, this work presents Quditto as a hybrid QKD-PQC network emulation platform featuring automated and scalable cloud-native orchestration. The proposed platform introduces four principal contributions: a cloud-native orchestrator enabling fully automated infrastructure deployment across cloud and multi-cluster environments; an optimized provisioning workflow enabling large-scale quantum-safe network emulation; native integration of post-quantum nodes enabling unified emulation of hybrid QKD-PQC networks; and a secure key management module providing persistent and access-controlled storage of cryptographic material. Experimental validation demonstrates sublinear orchestration-time scaling with network size and successful end-to-end hybrid QKD-PQC key establishment on a representative spine-leaf deployment, thereby enabling the systematic evaluation of quantum-safe networking mechanisms in large-scale heterogeneous network environments.

Abstract: Given an undirected weighted graph $G$, a $γ$-approximate low-stretch spanning tree (LSST) $T \subseteq G$ is a tree that approximates the distance metric of $G$ up to a $γ$-factor in expectation. Currently, existing algorithms to find a provably good LSST carefully construct an approximate shortest-path tree from an arbitrary source. The resulting algorithms are intricate. In contrast, practitioners observed that a much simpler heuristic performs surprisingly well: choose an arbitrary root, run Dijkstra's algorithm, and use the resulting shortest-path tree as an LSST. In this paper, we give a smoothed analysis of shortest-path tree algorithms, such as Dijkstra's algorithm, that explains this behavior. We show that adding a small perturbation to the weights of the input graph suffices to turn the shortest path tree rooted at an arbitrary node in the resulting graph into an $\tilde{O}(1)$-approximate LSST. We further show that the set of perturbations can be computed efficiently from few low-diameter decompositions (LDDs). Thus, our proof is also constructive in the sense of giving a novel approach to computing LSSTs.

Abstract: Graph neural networks (GNNs) need to exploit improved message passing without surrendering control over predictions already trusted in deployment. We introduce Reference-Tail Trust (RTT), a framework that admits learned updates inside a frozen GNN and certifies the prediction actually served. RTT couples graph-based proposal states with a constrained internal optimizer: each displacement is charged for its worst-case terminal cross-entropy increase through the incumbent's remaining message-passing layers. A trajectory-validated tube and an independent checker enforce per-node probability floors, $p^{\mathrm{s}}_{ic} \ge e^{-H_{\mathrm{row}}} p^{\mathrm{r}}_{ic}$, and a call-level budget, $\sum_i w_i D_\infty(p^{\mathrm{r}}_i \| p^{\mathrm{s}}_i) \le H^+$, uniformly over labels. Calls whose adapted outputs pass certification require no separate full incumbent rollout; failed certificates trigger whole-call fallback. We derive the exact probability-floor frontier by water-filling, characterize architecture-constrained efficiency, and establish conditions under which internal propagation exploits evidence unavailable to restricted output correctors. In the reported ogbn-arxiv audit, RTT achieves $6.5\times 10^{-3}$ nats of mean gain per call, with a one-sided 95% regression-rate upper bound of 0.95% and a 95% negative-flip upper bound of 0.51% on the uninspected part of the reserved node population. Its mean gain is 61% of a cross-fitted posterior-based frontier estimate and exceeds the strongest matched one-pass corrector by $+0.9\times 10^{-3}$ nats. Reported experiments span eight proposals, six graph-incumbent families, structural and temporal graph shifts, and molecular prediction, with additional image and tabular evaluations. RTT makes GNN adaptation a budgeted, certifiable inference decision rather than an unconditional model replacement.

Abstract: We give a randomized polynomial-time algorithm that, for every fixed $\varepsilon > 0$, colors every $3$-colorable $n$-vertex graph using $O\bigl(n^{(13-\sqrt{97})/18+\varepsilon}\bigr) \approx O\bigl(n^{0.17506+\varepsilon}\bigr)$ colors, improving upon the previous best bound of $O(n^{0.19539})$ from Bansal, Huang, and Lee. Our improvement comes from analyzing higher-level neighborhoods through a recursive description of failure in Gaussian SDP rounding. If the rounding returns too small an independent set, it produces local Gaussian certificates at every vertex of a nonempty induced subgraph. We propagate these certificates along walks to higher-level neighborhoods by defining a recursive certificate structure and proving a strengthened cover-composition lemma, which refines the one of Arora, Chlamt{á}{č}, and Charikar. We then construct a bounded potential function that increases by a fixed positive amount at every propagation step, yielding a contradiction. Consequently, the rounding must produce a sufficiently large independent set.

Abstract: Graph Neural Networks (GNNs) are widely used for representation learning on graphs, but most methods assume static topologies, making them inefficient on evolving networks where edges change over time. Existing dynamic approaches either model graph evolution through temporal GNN architectures without focusing on efficient dynamic maintenance, or are restricted to linear propagation models based on Personalized PageRank. In this work, we study how to efficiently maintain node representations for non-linear GNN propagation under edge insertions and deletions. The propagation has no learned parameters, and only a classifier applied afterward is trained. For a broad class of standard activation functions, we develop a residual-based dynamic algorithm that selectively propagates local errors via push operations, maintaining an approximation to the evolving fixed point without full recomputation. We prove that our method achieves amortized $O(1/ε)$ update time per graph change under a degree-normalized error guarantee. Our approach uses a potential-based analysis in a degree-scaled norm and, in contrast to prior work on the linear case, requires no randomness assumptions on either the update sequence or the input vector. For the linear special case, we additionally provide an exact dynamic algorithm via low-rank matrix inverse updates. Experiments on benchmark datasets show that incorporating non-linearity improves accuracy while preserving efficient update performance, yielding a scalable and theoretically grounded method for maintaining this propagation on dynamic graphs.

Abstract: Learning-augmented algorithms use machine-learned predictions to improve classical algorithmic guarantees when the predictions are accurate, while retaining rigorous performance guarantees when they are not. We study this paradigm for search on trees. Given a tree $T$ containing an unknown target vertex $t$, an algorithm may query any vertex $v$ and learn which neighbor of $v$ lies on the unique path from $v$ to $t$. The goal is to find $t$ using as few queries as possible. We consider the distributional setting, in which the target is drawn from an unknown distribution $p$ and the algorithm is given a predicted distribution $\widehat p$ of unknown quality. We give an algorithm with expected query complexity $O\left(H(p)+k\log η\right)$, where $H(p)$ is the Shannon entropy of the true distribution and $η$ is the earth mover's distance between $p$ and $\widehat p$ in the tree metric. We also provide a matching lower bound that shows our algorithm is asymptotically tight. Finally, experiments on real-world and synthetic trees show that our prediction-based algorithm can use substantially fewer queries than a simple baseline that trusts the prediction completely.

Abstract: The Simultaneous Authentication of Equals (SAE) protocol, introduced in WPA3, provides robust protection against offline dictionary attacks against a network Pre-Shared Key (PSK) and also protection of session keys from other people knowing that PSK. However, its high computational cost for the Password Element (PE) derivation makes Access Points (APs) vulnerable to CPU exhaustion Denial-of-Service (DoS) attacks. This paper proposes a resilient architectural modification to SAE. First, we introduce an asymmetric resource cost model that offloads the iterative discovery of cryptographic elements to the client, allowing the AP to maintain a fixed computational load during the handshake. To further mitigate brute-force attempts, we implement a mechanism based on a slow-path key derivation (with variable cost key derivation functions, such as PBKDF2 or Argon2), incorporating a deliberate processing delay on the supplicant. Finally, we introduce a ticket-based mechanism to facilitate efficient re-authentication for known devices, bypassing expensive exchanges while preserving system availability under adversarial conditions. Experimental results demonstrate that this architecture significantly mitigates DoS risks without compromising legitimate network access.

Abstract: Given an undirected weighted graph $G=(V,E)$ on $n$ vertices, the classical Gomory-Hu tree of $G$ is a structure that encodes an arbitrary minimum $s,t$-cut for every $s,t\in V$ using just $O(n)$ space. In this work, we ask whether the same compactness is achievable for the natural and structured family of all-pairs \textit{nearest minimum cuts}. The nearest minimum $(s,t)$-cut is the unique inclusion-wise minimal one among all minimum $s,t$-cuts containing $s$. This family has proven useful in a wide range of applications, including fault-tolerant reachability, minimum cut sensitivity oracles, cactus representations, and fast Gomory-Hu tree constructions. Despite its fundamental role, no subquadratic space representation is known for them to date. The $O(n)$ space representations are known only in single-source settings, where given a source $s$, one can report the nearest minimum $(t,s)$-cut for any $t\in V\setminus \{s\}$. We close this gap by presenting the first optimal space representation of all-pairs nearest minimum cuts, providing a natural analogue of the Gomory-Hu tree. Our main result is an $O(n)$ space structure that encodes the nearest minimum cut between every pair of vertices. Furthermore, given any pair $s,t\in V$, it can report the nearest minimum $s,t$-cut in $O(n)$ time. Both bounds match those of the Gomory-Hu tree and are worst-case optimal. As an application, we design an all-pairs minimum cut sensitivity oracle for edge insertion: a data structure that occupies $O(n)$ space and, given any edge $e$, can determine for all pairs $s,t\in V$ whether the minimum $s,t$-cut value increases upon insertion of $e$ in $O(n^2)$ total time. Existing insertion sensitivity oracles were either limited to the single-source setting or used $O(n^2)$ space for all-pairs [Baswana, Gupta, and Knollmann, Algorithmica'22; Baswana and Pandey, SODA'22].

Abstract: Wireless local area network (WLAN) performance is jointly shaped by medium contention, propagation, Wi-Fi configuration, and transport-layer behavior. This study evaluates IEEE 802.11g and IEEE 802.11ax in a single-access-point uplink topology, comparing UDP and TCP under Friis, LogDistance, and cascaded Friis-Nakagami propagation models. The factorial design spans 5 to 50 stations, six access-point distances from 5 m to 50 m, and three random seeds. Of 1,080 scheduled executions, 1,073 produced valid CSV outputs; seven runs terminated with internal ns-3 and cppyy segmentation errors and were excluded. Across the global scenario summaries, TCP FlowMonitor packet delivery ratios (PDRs) range from 0.994 to 0.997, whereas UDP PDRs range from 0.298 to 0.731. The highest mean aggregate throughput is 2.619 Mb/s for TCP under the configured IEEE 802.11ax mode with Friis propagation; UDP reaches 25.854 Mb/s in the same topology. These results show that packet delivery ratio, throughput, delay, and fairness must be considered together. FlowMonitor metrics are IP-flow observations, so the study does not establish application-level delivery or isolate optional IEEE 802.11ax multi-user mechanisms.

Abstract: It is well known that the \Lovasz-Theta function of a random graph $G(n,\tfrac{1}{2})$ is $Θ(\sqrt{n})$. More precisely, it is tightly concentrated in the interval \( [\sqrt{n},\, 2\sqrt{n}], \) where the upper bound follows from an explicit dual witness for the associated semidefinite program. Numerical evidence and heuristic arguments suggest that the true value is $(1+o(1))\sqrt{n}$. However, closing this gap has remained a longstanding challenge, resisting existing techniques even in light of recent progress on sharp algorithmic thresholds and non-asymptotic free probability. In this work, we resolve this question by proving that the \Lovasz-Theta function of $G(n,\tfrac{1}{2})$ is $(1+o_n(1))\sqrt{n}$ with high probability, determining its asymptotic value up to vanishing relative error.

Abstract: We prove the coarse Erdős-Pósa conjecture of Georgakopoulos and Papasoglu. Informally, any graph either contains many fat cycles that are pairwise far apart, or there is a small number of bounded radius balls that together hit all of them. To be more precise, if $G$ is a graph with no $q$-fat model of $k \cdot K_3$ for some $q, k \in \mathbb{N}$, then there is a set $X\subseteq V(G)$ of $\mathcal{O}(k\log k)$ vertices such that every $q$-fat model of $K_3$ in $G$ has distance $\mathcal{O}(q)$ from $X$. In another form more closely resembling Manning's theorem that characterises quasi-trees: if $G$ is a graph with no $q$-fat model of $k \cdot K_3$ for some $q, k \in \mathbb{N}$, then $G$ is $\mathcal{O}(q)$-quasi-isometric to a graph $H$ that contains a set $X\subseteq V(H)$ of $\mathcal{O}(k\log k)$ vertices such that $H-X$ is a forest. Bootstrapping this result, we further prove that every graph with no $q$-fat model of $k \cdot K_3$ is quasi-isometric to a graph with no $k \cdot K_3$ minor, where the quasi-isometry can be chosen to only have additive distortion. This result also holds for $k = \infty$. We also obtain an Erdős-Pósa theorem for long induced cycles that are far apart.

Abstract: We study the distributed average consensus problem under persistent link-level disturbances modeled as a martingale difference sequence with uniformly bounded conditional second moments. Under such disturbances, the standard stochastic-approximation-based linear iteration with diminishing stepsizes drives the network to consensus on an unbiased random variable with non-vanishing variance instead of the exact initial average. To understand and resolve this limitation, we develop an anchoring-based mechanism derived from a decentralized gradient descent formulation and study the effect of incorporating a decaying anchoring term that continuously pulls each agent state toward its initial value. This perspective provides an intuitive interpretation of how state anchoring counteracts disturbance accumulation. Under standard summability conditions, we prove that the resulting algorithm achieves exact average consensus almost surely. Furthermore, this decentralized gradient perspective offers a unifying framework for several related methods and an interpretable design principle for exact average consensus under persistent disturbances.

Abstract: Let $G$ be the line graph of a finite simple graph, with $n\geq1$ vertices and maximum degree $Δ$. We prove that single-site Glauber dynamics for uniform proper $q$-colorings mixes in $O_Δ(n\log(n/\varepsilon))$ steps for every integer $q\geqΔ+5$. Our proof uses the Bochner framework of Chen and Liu (2026).

Abstract: The stochastic block model is a paradigmatic model of networks with community structure. Yet percolation in the model has been studied primarily in cases with a fixed block structure, even though in real networks, the community structure may evolve as the network grows. Here we study percolation in sequences of stochastic block models in which the numbers and sizes of communities, as well as the intra- and intercommunity connection probabilities may all change with the network size. We analyze five such sequences using two methods: linearized self-consistent equations for the locally tree-like models and a branching process at the community scale for the models with nonvanishing clustering. We find that the critical average degree is not generally equal to $1$, even in locally tree-like sequences, because the transition depends on how connections are distributed across the evolving community structure. We also show that the community-scale branching process accurately predicts the transition when intercommunity connections are sufficiently sparse, even in the presence of nonvanishing clustering, while a geometric stochastic block model sequence demonstrates the limitations of this method when correlations between intercommunity connections cannot be neglected. These results extend percolation studies in the stochastic block model to more realistic scenarios with evolving community structure, and may provide new methods to derive the upper and lower bounds for the percolation threshold in geometric long-range percolation.

Abstract: We study prophet inequalities for a random walk reward stopping problem with sample-based information. The goal is to stop as close as possible to the maximum of a random walk with i.i.d. increments, measuring performance by the ratio between the expected reward when stopping and the expected true maximum. We consider a sample-based model in which the increment distribution is unknown and the decision maker has access to $K$ independent sample paths of the reward process. For the infinite-horizon setting, we establish a sharp prophet inequality with constant $(K/(K+1))^{K+1}$. The guarantee is attained by a randomised stopping rule based on the ladder height decomposition of random walks. As $K\to\infty$, this recovers the classical $1/e$ prophet inequality from the full-information setting. For the finite-horizon setting, where the process terminates after $n$ steps, we first prove a tight no-information prophet inequality with constant $1/H_n$, where $H_n$ is the $n$-th harmonic number. For $K\ge1$ samples, we show that a prophet constant of $1/4$ is attainable. Finally, we prove that, with $K$ samples, the prophet constant is at most $(K/(K+1))^{K+1}+(6+6H_K)/H_n$ for $n\ge 2K^2$, implying convergence to the infinite-horizon constant as $n\to\infty$. Our approach combines random walk theory, including ladder heights and Spitzer's identity, with linear programming duality. Our results contribute to random walk stopping theory and to sample-based prophet inequalities for correlated rewards, an area that remains largely unexplored. To the best of our knowledge, our tight sample-based prophet inequalities are the first whose performance is parameterised exactly, rather than only up to constants, by the number of available samples.

Abstract: Graph Incremental Learning has garnered increasing attention as dynamic graph data continues to emerge across diverse fields. Conventional approaches primarily address catastrophic forgetting by preserving node-related knowledge through replay or distillation techniques; however, they often incur high computational costs and inefficiency. This issue is further exacerbated in real-world scenarios where labeled data for new classes is scarce. In this paper, we propose a novel lightweight plastic-memory framework specifically designed for few-shot incremental learning on graphs. The core idea of our framework is the construction of a plastic-memory module that evolves over time, continuously updating and expanding its memory to accommodate new classes while retaining previously learned knowledge. In contrast to existing techniques, our memory module is both lightweight and effective, featuring an innovative evolving micro-clustering structure that dynamically updates representations of class prototypes, sub-prototypes, and their interaction weights. Building on this memory module, we introduce a memory-driven meta-learning framework that enhances adaptability to new tasks in its inner loop while maintaining stability for earlier tasks in the outer loop. Extensive experiments on four benchmark datasets demonstrate the framework's superior performance in balancing stability for old knowledge and adaptability to new knowledge.

Abstract: The capacity $C(d)$ of the i.i.d. binary deletion channel exists by Dobrushin's information-stability theorem, but no closed form is known. Classical constructive lower bounds from i.i.d. run-length coding have been evaluated only for one- or two-parameter families (geometric, Markov, or Morse-type). We show that the same infinite-blocklength functionals become strictly stronger when the run-length law $P$ is treated as a free distribution and optimized by learning. We reduce the Drinea--Mitzenmacher functional to a bilinear form in $P$ and prove that finite-support truncation is one-sided, so computed values remain valid lower bounds. We extend the Venkataramanan et al. reductions from geometric runs to arbitrary finite-support laws, including a residual-run HMM for output-bit entropy. Softmax gradient ascent searches $P$; every reported number is a fresh one-sided evaluation of the formula, with no Monte Carlo and no finite length-entropy penalty. The envelope of the two optimized bounds exceeds Gallager's $1-h(d)$ (for $d<1/2$) and the tabulated bounds of Drinea--Mitzenmacher, Venkataramanan et al., and Rubinstein--Con at every tested $d$. Representative values: $C(d)\ge 0.92212$, $0.72939$, $0.56486$, $0.35127$, $0.22616$, $0.10414$, $0.02891$, $0.01322$ at $d=0.01$, $0.05$, $0.10$, $0.20$, $0.30$, $0.50$, $0.80$, $0.90$. The largest absolute gain over that record is $3.7\times 10^{-3}$ bits (at $d=0.30$); the largest relative gain is $6.8\%$ (at $d=0.90$). For $d\le 0.45$ the envelope is the free-$P$ Venkataramanan functional; from $d=0.50$ it is the learned Drinea--Mitzenmacher law. At large $d$ the optimizer finds sparse run-length combs that parametric families cannot represent. A concurrent enclosure of Papailiopoulos is stronger on much of $[0,1]$, but our envelope remains larger at high $d$ (e.g. $0.02891$ vs $0.02884$ at $d=0.80$; $0.01322$ vs $0.01293$ at $d=0.90$).

Abstract: For a binary deletion channel operating on fixed-length inputs, the relevant figure of merit is the finite-blocklength capacity $C_N(d)=\max_{p(x^N)}\mathrm{I}(X^N;Y)$, not only the infinite-blocklength limit $C(d)$. We show that an optimal input may be chosen constant on complement and permutation-equivalence orbits, reducing the optimization to one weight per orbit, and introduce the optimized run distribution (ORD), an $N$-parameter run-count model that coincides with $C_N(d)$ for $N\le 3$ and is optimal among all run-count-constant inputs. An exact embedding-count dynamic program evaluates $\mathrm{I}$ for these structured laws. A hybrid neural--exact procedure recovers certified ORD weights for $N\le 8$; variational critics (InfoNCE, NWJ, DV/MINE, SMILE) are used only as inner search objectives. Direct score-function learning of ORD weights collapses toward a flat run-length distribution (RLD) for $N\ge 32$. We therefore introduce ORD continuum transfer: a normalized run-count profile learned from exact small-$N$ ORD solutions is resampled at target lengths up to $N=512$. Transferred ORD consistently outperforms RLD at moderate deletion probabilities; at $d=0.1$ the gain vanishes by roughly $N=128$--$192$. Exact ORD rates converted by Fertonani--Duman's length-entropy inequality are valid lower bounds on $C(d)$; nested-Monte-Carlo evaluations of large-$N$ inputs are reported as diagnostics and are not claimed as capacity lower bounds. A fixed-$N=100$ sample-budget study quantifies nested-MC bias. All primary reported rates are values of $\mathrm{I}(X^N;Y)/N$.

Abstract: In this paper, we present three new constructions of optimal FDRM codes, all derived from subcodes of maximum rank-distance (MRD) codes. The first construction (Theorem~\ref{theo5}) is based on a new family of generator matrices for systematic MRD codes and yields several previously unknown optimal FDRM codes. In particular, for $q\geq 7$, it establishes the optimality of $[\mathcal{F},7]_q$ FDRM codes with $ \mathcal{F}=[1,2,3,4,8,8,8,8,8]$, thereby resolving an open problem posed by Zhang \emph{et al.} (Des. Codes Cryptogr., 87(1):107--121, 2019). Our second construction exploits structural properties of generator matrices of a family of systematic MRD codes to obtain new optimal FDRM codes whenever each of the rightmost $δ-2$ columns of the Ferrers diagram $\mathcal{F}$ contains at least $n-1$ dots. Building upon this approach, we further develop a third construction by substantially relaxing this requirement: it is sufficient to assume that each of the rightmost $δ-2$ columns of $\mathcal{F}$ contains at least $n-r$ dots, where $r<κ$ and $κ=n-δ+1$. Furthermore, by exploiting the notion of proper combinations of Ferrers diagrams, we develop several recursive constructions that produce large FDRM codes from smaller building blocks, yielding a number of new optimal families. In particular, for an $n\times n$ Ferrers diagram $\mathcal{F}$ with prescribed parameters, one of these constructions establishes the optimality of $[\mathcal{F},\frac{n}{2}-1]_q$ FDRM codes whenever $n$ is even, thereby settling an open problem posed by Etzion \emph{et al.} (IEEE Trans. Inf. Theory, 62(4):1616--1630, 2016).

Abstract: The first almost-linear time maximum and minimum cost flow algorithm of Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva (FOCS 2022), reduced these flow objectives to a sequence of min-ratio cycle problems. Solving this core primitive requires approximately minimizing the ratio of a linear gradient term and an undirected length term. In Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva (FOCS 2022) and the subsequent work of Chen-Kyng-Liu-Meierhans-Probst Gutenberg (STOC 2024), intricate data structures were given to solve the min-ratio problem. We show that such a cycle can be extracted directly from the dynamic distance oracle of Kyng-Meierhans-Probst Gutenberg (STOC 2024) using linearity. This simplifies previous algorithms that relied on multiple additional steps to extract the cycle, and can be seen as evidence that solving the min-ratio cycle problem really is all about distances. As a result, we obtain a faster primal maxflow and min-cost flow solver that also extends to incremental graphs.

Abstract: For an odd prime $p$, let $Γ(R)$ denote the zero-divisor graph associated with the finite local ring $R= \mathbb{F}_p[x]/\langle x^4 \rangle$, having $p^3 - 1$ vertices and size $|E(Γ(R))| = \frac{1}{2}(3p^4 - 4p^3 - p^2 + 2)$. Using an equitable 4-cell partition induced by the ideal filtration $\langle u^3 \rangle \subset \langle u^2 \rangle \subset \langle u \rangle$, we prove that $\operatorname{Spec}_A(Γ(R))$ decomposes into discrete levels $λ\in \{0, -1\}$ with multiplicities $p^3 - p^2 - 1$ and $p^2 - 3$, respectively, alongside three irrational roots of an irreducible cubic polynomial $P_3(λ) = 0$, yielding adjacency energy $ε(Γ(R)) = 4p^2 + \mathcal{O}(p)$. In contrast, the Laplacian spectrum is entirely integral: $\operatorname{Spec}_L(Γ(R)) = \{0^1, (p - 1)^{p^3 - p^2}, (p^2 - 1)^{p^2 - p - 1}, (p^3 - 1)^{p - 1}\}$. Consequently, the tree entropy satisfies $z(Γ(R)) = \ln p - \frac{1}{p} + \frac{\ln p}{p} + \mathcal{O}(\frac{\ln p}{p^2})$, with small-failure unreliability bounded by $p^2(p - 1)(1 - q)^{p-1}$. In linear consensus $\dot{x} = -Lx$, error trajectories decouple into three modal timescales $\{ (p^3 - 1)^{-1}, (p^2 - 1)^{-1}, (p - 1)^{-1} \}$ with algebraic connectivity $α(Γ(R)) = p - 1$ and steady-state $H_2$ error variance $H_2^2 = \frac{Kf(Γ(R))}{2n^2} = \frac{1}{2p} + \mathcal{O}(p^{-3})$. Furthermore, the Kirchhoff index yields a vanishing average resistance distance $\overline{r}(Γ(R)) = \frac{2}{p} + \mathcal{O}(p^{-3}) \to 0$, while unbiased Markovian random walks induce an asymptotic traffic concentration vector $Π= (\frac{1}{3}, 0, \frac{1}{3}, \frac{1}{3})$ with quadratic per-node core routing stress $π_{\mathrm{core}}/π_{\mathrm{periph}} \sim p^2 + p + 1$.

Abstract: To speed up algorithms on geometric graphs, it is common to approximate the complete Euclidean graph while maintaining certain geometric properties. A (directed) $t$-spanner $G$ for a point set $P$ in the Euclidean space is a (directed) graph such that for every pair of points, the shortest path in $G$ is at most a factor $t$ longer than the Euclidean distance between those points. In this paper, we investigate $t$-spanners that are bounded by certain graph parameters. Let $κ$ be a graph parameter. We show that for path-width, branch-width and cut-width there is an $\mathcal{O}(n/k^{d/(d-1)})$-spanner $G$ on $P$ with $κ(G)=k$ and that this is asymptotically worst-case optimal. In $\mathbb{R}^2$ we show the same bounds for planar graphs of clique-width or rank-width $k$. In contrast, for tree-depth, we show that there are sets of points for which the dilation cannot be bounded. Therefore, we investigate computing a spanner with tree-depth $k$ and minimum dilation. We show that already for tree-depth $3$ this problem is NP-hard to approximate within any factor strictly less than $\sqrt{2}$, and present an XP-algorithm to compute for a given tree-depth $k$ a graph with dilation at most $2t^*$, where $t^*$ is the minimum dilation. We further extend these results to obtain directed $\mathcal{O}(n/k^{d/(d-1)})$-spanners $G$ with $κ(G)=k$ for $κ$ being directed tree-width, directed path-width or DAG-width and show that also in the directed case, this is asymptotically worst-case optimal.

Abstract: For every fixed activity $λ>0$, we establish three results for the monomer--dimer model on an $n$-vertex simple graph $G$ with $m\ge1$ edges and maximum degree $Δ$. 1. Near-linear mixing and sampling. Single-edge Glauber dynamics has mixing time $O_λ(m[\log^2 n+\log(1/\varepsilon)])$, giving a near-linear-time approximate sampler. 2. Work-efficient parallel sampling. We simulate the same Glauber dynamics in parallel using $\tilde{O}_λ(m+n)$ work and $\tilde{O}_λ(\min\{Δ,m^{1/3},\sqrt n\})$ depth with high probability. 3. Fast approximate counting. We estimate the partition function within relative error $\varepsilon$ in $\tilde{O}_λ(n^2/\varepsilon^2)$ work. For dense graphs with $m=Θ(n^2)$, this is near-linear in the input size. For the mixing theorem, we establish a general log--Sobolev criterion based on field-dynamics spectral stability, with only logarithmic dependence on the inverse occupied-marginal lower bound. Parallelism uses a matching-specific analysis of occupation-interval dependencies. Counting uses monomer-preconditioned Jerrum--Sinclair dynamics, whose parameters are learned efficiently by Glauber dynamics.

Abstract: Consensus protocols ensure the robustness and scalability of blockchains and decentralized applications built on them. However, existing consensus mechanisms often impose high computational cost or require heavy communication overhead. To address these challenges, we propose proof of verifiable delay (PoVD), a lightweight consensus protocol based on the verifiable delay function (VDF). We present the detailed protocol of PoVD, including the block mining and verification rules, and illustrate how PoVD can flexibly adjust the block time distribution according to the network condition. Through mathematical proof, we point out that, under a relatively weak network assumption, PoVD can achieve a lower fork rate than PoW while maintaining the same throughput. Our experiments verify that PoVD exhibits low computation and communication complexity and can also improve the blockchain consistency, making it particularly suitable for resource-constrained nodes and bandwidth-limited networks.

Abstract: Let $A_1,\ldots,A_N$ be positive semidefinite matrices of rank at most $r$, with $\sum_iA_i=I$ and $\|A_i\|\le\varepsilon$. We prove that the original matrices admit signs with discrepancy $O(\sqrt\varepsilon\log(2r))$, independently of their dimension and number which is a significantly stronger result than what was known existentially. We give a deterministic algorithm with polynomial real-arithmetic work, and a separate existence proof requiring no computational assumptions. This extends our companion paper on rank-one Kadison--Singer discrepancy. A concave matrix power interpolates between the trace source, which pays a factor $r$, and the sandwich source, whose density response is harder to control. We prove that source concavity controls this additional response in the same inverse-Sylvester metric as the optimized spectral potential. As an application, a single spanning tree can be chosen simultaneously $O(\varepsilon\log^2(2s))$-spectrally thin for $s$ positive edge weightings of a common graph, provided every edge has leverage at most $\varepsilon$ in every weighting. The reduction preserves one common selection decision per edge. For incidence matrices with at most $t$ ones in every row and column, the diagonal specialization gives a deterministic walk on fractional colorings with discrepancy $O(\sqrt t\log(2t))$. The local-walk mechanism gives both existence and an efficient construction without using the Lovász local lemma. A Lean formalization of our existence proof has been completed and will be released shortly.

Abstract: A search tree on trees (STT) is a data structure for performing a search for a target vertex in a reference tree. A standard binary search tree is a special case of an STT, where the reference tree is a path of totally ordered elements. In this paper, we study the problem of succinct representation of STTs. We consider two cases: (1) general search trees on trees, and (2) Steiner-closed search trees on trees [Bose et al. TALG 2023]. For both cases, we present representations that can be constructed in polynomial time and achieve optimal space up to the lower-order additive terms. We also present data structures for supporting fast traversals of both general and Steiner-closed STTs. For general STTs our data structure still takes optimal space up to lower-order additive terms.

Abstract: As digital commerce ecosystems expand into low-end consumer electronics (CE), hardware constraints-specifically limited CPU duty cycles and volatile heap fragmentation-become significant bottlenecks for complex transactional flows. Traditional on-device middleware requires high "network chattiness" to manage multi-step state machines, leading to increased latency and potential transaction failure on unstable residential networks. This paper proposes a novel Transactional Backend-for-Front-End (T-BFF) Orchestration Framework designed for resource-constrained embedded platforms. By migrating the transactional state machine and microservice orchestration to a cloud-side layer, we achieve a significant reduction in client-side overhead. Our framework introduces a "Double-Handshake" protocol utilizing non-volatile flash memory for state recovery after hardware reboots. Experimental results on an ARM Cortex-A53 platform demonstrate a 35% reduction in maximum heap usage and a 40% improvement in end-to-end transaction latency. This framework provides a scalable, sustainable blueprint for maintaining transactional integrity on legacy hardware in the 2026 IoT landscape.

Abstract: Computing is evolving rapidly to cater to the increasing demand for sophisticated services, and Cloud computing lays a solid foundation for flexible on-demand provisioning. However, as the size of applications grows, the centralised client-server approach used by Cloud computing increasingly limits the applications' scalability. To achieve ultra-scalability, cloud/edge/fog computing converges into the compute continuum, completely decentralising the infrastructure to encompass universal, pervasive resources. The compute continuum makes devising applications benefitting from this complex environment a challenging research problem. We put the opportunities the compute continuum offers to the test through a real-world multi-view detection model (MvDet) implemented with the FastFL C/C++ high-performance edge inference framework. Computational performance is discussed considering many experimental scenarios, encompassing different edge computational capabilities and network bandwidths. We obtain up to 1.92x speedup in inference time over a centralised solution using the same devices.

Abstract: The paper presents a one-pass algorithm in the insert-delete graph stream model that returns a $(1+\varepsilon)(α+2)$-approximation for the size of the maximum matching in a graph of arboricity at most $α$. The algorithm uses $O(\varepsilon^{-4/3}α^{4/3}n^{2/3} \text{polylog} n)$ space. For constant $α$ and $\varepsilon$, this improves the best known previous space bound from $O(n^{4/5} \text{polylog} n)$ to $O(n^{2/3} \text{polylog} n)$. The algorithm is a linear sketch and requires no bounds on the number of deletions or on the arboricity of intermediate graphs.

Abstract: A \emph{directed feedback vertex set} of a digraph is a set of vertices whose removal destroys all directed cycles. The \textsc{Directed Feedback Vertex Set} (\textsc{DFVS}) problem asks for such a set of minimum cardinality or minimum total weight. Although general \textsc{DFVS} admits no constant-factor approximation under the {Unique Games Conjecture}, tournaments admit a randomized factor-$2$ approximation due to Lokshtanov et al. [SODA'20]. We extend this guarantee to two broader classes of structured digraphs, both of which also contain sparse digraphs. Our first and main result is a randomized polynomial-time factor-$2$ approximation for weighted \textsc{DFVS} on \emph{locally semicomplete digraphs} (\textsf{LSD}s), a class that strictly generalizes semicomplete digraphs and tournaments. To the best of our knowledge, this is the first non-trivial constant-factor approximation for \textsc{DFVS} on \textsf{LSD}s, even in the unweighted setting. Our second result is a randomized polynomial-time factor-$2$ approximation for weighted \textsc{DFVS} on \emph{quasi-transitive digraphs}, improving the recent deterministic $9/4$-approximation of Ghorbani and Mnich~[ICALP'26]. The algorithm follows from a simple recursive application of our composition framework. The factor $2$ is optimal under the {Unique Games Conjecture}, since tournaments are subclass of \textsf{LSD}s as well as quasi-transitive digraphs.

Abstract: The rise of large satellite constellations and Distributed Space Systems (DSS) demands generalized frameworks that enable fault-tolerant, autonomous distributed space applications. Conventional ground-centric command and control does not scale to systems of tens or hundreds of satellites, motivating the adoption of distributed computing. This paper introduces a conceptual distributed computing framework for satellite swarms, covering distributed state, command and control, and scientific mission. As a first validation step, a strongly eventually consistent distributed state service is designed and implemented using Conflict-free Replicated Data Types (CRDT), specifically a Last-Write-Wins Register-based key-value store. The service is evaluated in the context of Space Situational Awareness catalog dissemination across a simulated 66-satellite constellation emulated with GoNetEm. Results show that the CRDT-based approach reduces ground-to-satellite communication from 66 messages to a single uplink per update, with tree traversal matching the total message count of direct uplink. Under concurrent updates, sub-linear inter-satellite message growth is observed as nodes discard outdated versions, further reducing network overhead. These results demonstrate the viability of a CRDT-based distributed state as a scalable and fault-tolerant foundation for satellite swarm applications.

Abstract: We establish a degree-independent bound on spectral independence for log-concave Holant problems on simple graphs. As a corollary, we obtain relaxation-time bounds for Glauber dynamics of $O_λ(m)$ for the monomer-dimer model at activity $λ$ and $O_{b,λ}(m)$ for $b$-matchings at fugacity $λ>0$, where $m$ is the number of edges. For uniform $b$-matchings, the relaxation-time bound improves to $O(bm)$. The main proof ideas were found using GPT-5.6 Sol.

Abstract: Random walks are a standard tool for search problems in which a state can be updated locally and tested for being marked. When updating the state and checking whether it is marked have different costs, two classical strategies optimize different parts of the cost: checking after every step is optimal in the number of updates, while repeatedly checking only after mixing is optimal in the number of checks. For a single marked state $m$ and a walk started from its stationary distribution $π$, Dohotaru and Høyer stated that both guarantees can be matched simultaneously, for a walk that checks after blocks of a fixed length; their argument is sketched through quantum walks, and they observe that they know of no classical proof. We give a short and self-contained classical proof of such a tradeoff, for arbitrary irreducible Markov chains. The algorithm replaces the original transition matrix $P$ by the averaged walk $ \overline P_τ= \frac{1}τ\sum_{k=1}^τ P^k, $ where $τ$ is of order $π(m)HT(m)$. Using a coupling with the original walk and Kac's lemma, we prove directly that the averaged walk hits the marked state in $O(1/π(m))$ checks in expectation. The resulting search cost is \[ S + O(HT(m))U + O(1/π(m))C \] in expectation, where $S$, $U$, and $C$ denote setup, update, and checking costs.

Abstract: We present a counterexample to the relay channel capacity characterization proposed in a recent work, which is based on properties of typical sequences. The counterexample uses a binary relay channel with a noiseless source-destination component and binary symmetric relay links. An achievable scheme exceeds the proposed capacity characterization, thereby disproving the characterization of the capacity for general relay channels. We highlight that the counterexample is obtained with the assistance of ChatGPT-6 Astra and the proofs are simplified with human effort.

Abstract: A \emph{linear sketch} is a randomized linear mapping of a vector $v$ to a lower dimensional sketch vector, designed to preserve relevant information about $v$. We consider sketches of vectors $v \in Z^u$ (for $u \in N$), designed for exact recovery of $v$ from its sketch. Concretely, our \emph{Stuffed IBLT} is a linear sketch configured with a capacity $n \in N$ and a multiplicity limit $L \in N$ and will recover $v$ with high probability whenever $||v||_0 \leq n$ and $||v||_\infty \leq L$. The sketch can be maintained efficiently under unrestricted updates to $v$, i.e., $v$ is not subject to any constraints in between decoding requests. This makes the sketch useful for streaming algorithms and for solving the (multi)set reconciliation problem. For any positive constants $c$, $ε$, and for large enough $n$ and $u \geq n^{1+Ω(1)}$, the space usage of a Stuffed IBLT is within a factor $1+ε$ from the information-theoretic optimum while allowing updates in constant time, and decoding in time $O(n)$ with failure probability $n^{-c}$. This improves the space/time/error probability trade-off over all prior constructions with similar functionality, including the Invertible Bloom Lookup Table (IBLT). The performance of the Stuffed IBLT is essentially the best we could hope for, up to the dependence on $c$ and $ε$. We make the dependence on these parameters explicit, and further show a lower bound demonstrating that the dependence on $c$ is optimal within the class of peeling-based approaches. Our improvement comes from a careful combination of Walzer's spatial coupling technique (SODA '21), the purity heuristic of Houen, Pagh, and Walzer (SOSA '23), and backyarding (Belazzougui, Kucherov, and Walzer, ESA '24; Fleischhacker, Green Larsen, Obremski, and Simkin, ICALP '24), allowing us to eliminate bottlenecks of past approaches.

Abstract: Fully encrypted protocols (FEPs) provide encrypted channels that make all protocol-generated bytes computationally indistinguishable from uniform random strings. Several previous works have explored security definitions and constructions of unidirectional FEPs: protocols in which one party acts only as a sender, and the other acts only as a receiver. However, most applications require two-way information exchange, and a network adversary can observe communication in both directions and their shared lifetime. Because the semantics of bidirectional channels involve more complex shared state, it is possible that the ``naïve'' composition of two unidirectional channels can result in a two-way protocol that can be detected based on dependencies between the two directions, such as traffic imbalance, channel closure, failures, or connection tear-down. To address this issue, we introduce new formal security definitions for bidirectional FEPs that capture exact shaping, delivery, protocol-state integrity, private half-close, and cross-direction isolation, while revealing a public ``sending schedule'' and ``closing epoch'' that may be randomized. We show that the trivial composition fails to meet these definitions, leading to practical detection attacks. We then construct provably secure bidirectional FEPs (BiFEPs) for both the datastream and datagram settings. For datastream, we combine two direction-separated FEPs with a ``wrapper'' layer that prevents detection based on the mismatch between uni- and bi-directional connection states. For datagram, we add encrypted DATA/FIN/ACK with replay protection and loss-tolerant close. We validate the design through a Rust implementation and show that none of the surveyed deployed protocols provides the full set of BiFEP security properties.

Abstract: We present Budgeted Express-Mesh, a topology-routing co-design that adds a small number of traffic-aware express links under a fixed wire budget. An ASPL-based greedy placement is refined by simulation-guided annealing, while packets use committed top-K routes selected from delayed express-link congestion and reservation signals. Across four synthetic workloads, optimized placements consistently improve high-load throughput over Mesh and random placement, and annealing further improves Greedy. The gains persist under delayed quantized congestion information, longer express-link latency, multi-flit packets, and a 16-by-16 heterogeneous workload.

Abstract: Frequency Range 3 (FR3), 7.125-24.25 GHz, regarded as the "golden band" for 6G networks, has less challenging propagation characteristics than FR2 while offering much wider bandwidth for high data rate applications than FR1. Reusing existing FR1 infrastructure for FR3 network deployments requires gNodeBs (gNBs) to employ antenna arrays and perform beam management, which has proven challenging at FR2. In this paper, we extensively study and characterize the beam management effort in an FR3 urban network, in terms of: beam alignment sensitivity, number of directional link opportunities, gNB handover and beam switch rates, and beam steering distance. Our results show that achieving a high and stable mobile throughput requires significant beam management effort across FR3 bands. While the beam tracking requirements are less stringent at the lower frequencies due to wider beams, the beam switching rate to a non-adjacent beam is relatively comparable at FR3 and FR2.

Abstract: Hypergraphs provide a natural framework for modeling higher-order relationships, but the development of spectral techniques with provable guarantees for general non-uniform hypergraphs remains challenging. Building on Banerjee's normalized adjacency matrix and Spiro's averaging-based diffusion framework, we develop a spectral framework for non-uniform hypergraphs and establish Cheeger's inequality for their conductance. A fundamental result in the spectral theory of hypergraphs asserts that, for every non-covering hypergraph, the second-smallest eigenvalue of its normalized Laplacian is at most one. This spectral characterization yields an improved Cheeger's inequality for non-covering hypergraphs, and we show that the resulting inequality is tight on both sides using cycle and cube hypergraphs. Our framework further yields higher-order Cheeger inequalities and provides theoretical guarantees for Fiedler's spectral partitioning algorithm, all in the setting of hypergraphs. Finally and most notably, we construct a new family of optimal hypergraph expanders that is tight for the Alon--Boppana bound.

Abstract: Emerging physical AI systems require low-latency, task-oriented video communication over unreliable channels. We propose a semantic-aware multi-level neural video coding method for robust low-latency video transmission over unreliable channels that are abstracted as multi-level packet erasure channels. Built upon the real-time DCVC-RT neural video codec, the proposed framework introduces a semantic- and feature-aware coding strategy that partitions encoded representations into packets carrying different levels of semantic and latent-feature importance and assigns these packets to different streams, each associated with a priority level when transmitted over unreliable communication channels. We also developed an error-resilient entropy model that removes inter-packet dependencies, allowing each packet to be decoded independently under packet losses. The complete system is trained end-to-end over the abstracted multi-level packet erasure channels, enabling learning of channel-aware representations together with importance-aware packet assignment while facilitating the network for differentiated packet prioritization. Experiments show that the proposed framework significantly improves robustness over baseline DCVC-RT under packet erasures, achieving graceful degradation in less important regions while better preserving task-relevant visual content.

Abstract: A perfect matching in an ordered graph is nonnested if no edge lies strictly inside another. We classify the smallest edge sets meeting every nonnested perfect matching on $2k$ ordered vertices. For $k\ge2$, these blockers have $k$ edges and belong to three explicit families, with $2^k+k-2$ members in total. The proof uses a minimum spanning tree of an auxiliary interval cut; its equality case also classifies the minimum blockers for concatenations of crossing matchings. The argument gives a deterministic algorithm that, from at most $k$ deleted edges, returns a minimum blocker description or an avoiding nonnested perfect matching in $O(k^2)$ word operations and $O(k)$ auxiliary words. We also give an injection from one of the blocker families into minimum blockers of $123$-avoiding permutation matrices. Beyond the perfect case, an explicit construction gives graphs with $(k-1)n+1$ edges and no nonnested $k$-matching for every $k\ge5$ and $n\ge2k+1$.

Abstract: In the $(p,q)$-Flexible Graph Connectivity problem, the input consists of non-negative integers $p$ and $q$ and a graph $G=(V, E)$ whose edges are classified into safe and unsafe edges with non-negative edge costs. A subgraph H of G is $(p,q)$-Flex-Connected if every non-empty proper subset of vertices has either at least $p$ safe edges or at least $p+q$ total edges crossing it. The goal is to find a minimum cost subset $F\subseteq E$ of edges such that the subgraph $(V, F)$ is $(p,q)$-Flex-Connected. We give a $(p+q)^{O(pq)}$-approximation for this problem, which in particular implies a constant approximation for every fixed constants $p$ and $q$. We achieve this by designing a $(p+q)^{O(pq)}$-approximation for the augmentation problem of finding a minimum cost subset of edges to add to make a (p,q-1)-Flex-Connected graph into a (p,q)-Flex-Connected graph. Underlying the augmentation algorithm is a structural result showing that all deficient cuts can be represented by min rooted-cuts in a $(p+q)^{pq}$-sized collection of digraphs. This structural result was discovered by ChatGPT Astra.

Abstract: Blocking flow-type maximum matching algorithms are based on finding maximal sets of shortest augmenting paths. They run in $O(m\sqrt{n})$ time, on both bipartite [HK73, Din70, Kar73a, Kar73a] and nonbipartite graphs [GT91, Gab17, Vaz24], but this time bound can be improved if the input is constrained. In this paper we consider $d$-regular bipartite and nonbipartite graphs. Previous algorithms show that a perfect matching in $d$-regular bipartite graphs can be computed in near-linear time deterministically [COS01] or sublinear time with high probability [GKK13]. On $d$-regular non-bipartite graphs, a $(1-1/(d+1))$-approximation can be computed in sublinear time $O(n \log n)$ with high probability [DH25], and hence a maximum matching can be computed in $O(n^2)$ time, w.h.p., which is slightly faster than the best deterministic algorithm for regular graphs [Yus13], running in O(n^2 log n) time. We prove that any blocking flow-type maximum matching algorithm based on finding shortest augmenting paths runs in $O(n^2)$ time on d-regular graphs, both bipartite and nonbipartite. On nonbipartite graphs this is an asymptotic improvement over $O(n^2 \log n)$ [Yus13] and an improvement over $O(m\sqrt{n})$ [GT91, Gab17, Vaz24] when $d = ω(\sqrt{n})$. It also improves [DH25] by making its $O(n^2)$ bound deterministic. However, the main take-away message is that no new algorithms are needed: the "classic" matching algorithms automatically outperform [Yus13, DH25]. We also consider extensions of our results to graphs that are only "nearly regular," meaning that their degrees all lie within a specified range, $[d, Δ]$.

Abstract: On evolving graphs, node classifiers must satisfy two key requirements: inductive generalization to newly arriving nodes under distribution shift and calibrated uncertainty for safety-sensitive applications. Standard graph neural networks (GNNs) are typically trained once and address neither requirement. We adapt the Bayesian last-layer (BLL) model by placing random last-layer parameters on top of a deterministic GNN encoder for uncertainty quantification. The categorical softmax likelihood required for classification breaks Gaussian conjugacy, so neither the training posterior nor the test-time streaming update has a closed-form solution. To address both challenges, we introduce a variational Bayesian last-layer (VBLL) objective that jointly trains the encoder and an approximate last-layer posterior by maximizing an evidence lower bound with a Monte Carlo expected log-likelihood. At test time, we freeze the encoder and apply an online Laplace update to the last-layer posterior. This update corresponds to a power-prior Bayesian model with exponential forgetting and a Kullback-Leibler anchor to the training posterior. Across five node-classification benchmarks under distribution shift, online GVBLL is the only method to achieve the best accuracy and negative log-likelihood on every dataset. It improves accuracy by up to 17 percentage points on Cora and 14 percentage points on ogbn-arxiv over the strongest non-GVBLL baseline, while remaining competitive in calibration with MC Dropout, Deep Ensembles, Temperature Scaling, and Gaussian-process classifiers.

Abstract: Federated learning over IEEE~802.11 shares the wireless channel among clients that send model updates. We use ns-3 to measure the frame-delivery ratio and saturation throughput for different client densities and offered loads. A separate FedAvg trainer uses the frame-delivery ratio as a first-order proxy for the update-admission probability and uses an equation to estimate communication time. The method does not simulate the delivery of a complete model update or measure end-to-end training time. Across 720 evaluated runs with two datasets, two data partitions, six client densities, six offered loads, and five seeds, all runs reached their predefined target accuracy within the round budget. Rounds-to-target changed little with offered load, while communication time-to-target increased by about two orders of magnitude across the client-density range. A Bianchi-anchored estimator produced a mean absolute percentage error from $2.3\%$ to $10.2\%$ on held-out configurations. This error is measured against communication time constructed from the same round-duration equation, not against independently measured completion time. We also compare uniform participation with persistent heterogeneous participation. The study does not detect a statistically distinguishable excluded-class accuracy gap over five seeds, but the confidence intervals are wide. The results apply only to the evaluated configurations and do not provide a general convergence or fairness guarantee.

Abstract: Finding large lattice subgraphs in sparse Erdős--Rényi random graphs is a classical problem at the interface of random graph theory and algorithms. General bounded-degree embedding and universality theorems give powerful results for broad graph families, but when specialized to square grids they operate at densities substantially larger than the grid-emergence scale. In this paper we exploit the specific geometry of the square grid. We introduce the Quarantined Local Search, a three-phase local algorithm that separates the construction of an initial boundary from the later corner-closure process and controls adaptive negative exposure through bounded pair-test histories. We prove that, for every fixed $δ\in (0,1)$, there exists $C_δ>0$ such that the algorithm embeds a $k\times k$ square grid with $k^2\le (1-δ)n$ in $G(n,p)$ with high probability whenever $p\ge C_δ\sqrt{\ln k/n}$. Thus, for $k^2=Θ(n)$, a density of order $\sqrt{\log n/n}$ is sufficient, a factor of order $\sqrt{\log n}$ above the corresponding $n^{-1/2}$ emergence scale.

Abstract: We determine a sharp threshold for the adaptable 2-colorability of a random graph equipped with a uniformly random, not necessarily proper, red/blue coloring of the edges. To accomplish this, we characterize a family of subgraphs along with edge colorings whose inclusion or exclusion determines adaptable $2$-colorability. We further show that above the threshold, a long path with alternating edge colors is formed. We use this path to prove the existence of such a subgraph in the supercritical regime. We then provide and prove symmetric bounds on the critical window for $2$-adaptable colorability. Particularly, we prove bounds matching that of the critical windows for the giant component in the Erd$ő$s-R$é$nyi random graph model as well as the satisfiability of a random $2$-SAT instance. Finally, we show that below the critical window, the solution space of adaptable $2$-colorings remains connected, that is one can travel from one adaptable $2$-coloring to another by a sequence of $2$-colorings which differ on $O(\log{n})$ many vertices.

Abstract: Strong Connectivity Augmentation (SCA) asks whether a directed acyclic graph can be made strongly connected by adding at most $k$ prescribed links whose total weight is within a given budget. Klinkby, Misra, and Saurabh (SODA 2021) gave an $O^*(2^{O(k\log k)})$-time algorithm and asked whether the problem admits a single-exponential parameterized algorithm and a polynomial kernel. We answer both questions affirmatively: SCA can be solved in $O^*(9^k)$ time and admits a polynomial kernel with $O(k^4)$ vertices and $O(k^{16})$ bits. For unweighted SCA, we obtain $O^*(4^k)$ time and a kernel with $O(k^3)$ vertices. Our algorithms are based on a particularly simple reduction to Strongly Connected Spanning Subgraph with two edge costs.

Abstract: This paper investigates the performance of high-altitude platform station (HAPS)-assisted communication systems employing either reconfigurable intelligent surfaces (RIS) or relay stations (RS) under non-orthogonal multiple access (NOMA) scheme. Practical system impairments, including hardware impairments (HWI) and imperfect channel state information (CSI), are explicitly considered. The results show that HAPS-RIS outperforms HAPS-RS in terms of both sum-rate and energy efficiency under non-ideal conditions due to its passive nature, which avoids noise amplification. Furthermore, it is demonstrated that RIS element allocation and user spatial distribution significantly impact NOMA performance, where increased user separation and proper allocation enhance channel disparity and improve system efficiency. Despite its higher sensitivity to imperfect CSI, HAPS-RIS can effectively compensate for performance degradation through large-scale RIS element deployment, maintaining a performance advantage over half-duplex RS-based systems. These insights provide useful design guidelines for impairment-aware HAPS-assisted 6G communication systems.

Abstract: We study the \emph{vantage point selection} problem, introduced by Ashvinkumar, Chowdhury, Gao, Goswami, Mitchell, and Polishchuk [WADS'25] to model the problem of estimating bottleneck capacities on the Internet. The input is a weighted undirected graph with unique shortest paths where every edge has a distinct unknown \emph{capacity}. When the algorithm \emph{queries} a vertex $v$, it reveals the minimum-capacity edge on the shortest path from $v$ to every other vertex reachable from $v$. The goal is to maximize the total number of revealed edges. The quality of an algorithm is measured by its competitive ratio against an optimal algorithm that knows all edge capacities a priori. We first consider the foundational single-query setting, where both the algorithm and the optimal algorithm are restricted to a single query. There is a trivial upper bound of $O(n)$ on the competitive ratio and the best known lower bound was $\tildeΩ(\sqrt{n})$. We provide an algorithm and matching lower bound (up to polylogarithmic factors) showing that the best possible competitive ratio is $\tildeΘ(n^{2/3})$. Furthermore, we extend our results to the general setting where the optimal algorithm is allowed $k$ queries and our algorithm is allowed $αk$ queries for $α\geq 1$. We present a randomized non-adaptive algorithm and matching lower bound (up to polylogarithmic factors) showing that the best possible expected competitive ratio for non-adaptive algorithms is the following surprisingly complex bound: $$ \tildeΘ\left( \min\left\{ \frac{n}{αk}, \max\left( \sqrt{\frac{n}α}, \frac{n^{2/3}}{αk^{1/3}} \right) \right\} \right). $$

Abstract: Let $λ$ be the minimum cut value of an $n$-vertex undirected multigraph. For every fixed $α>1$, we prove that there are $O(n^{\lceil2α\rceil-1})$ cuts of size strictly below $αλ$. The exponent is sharp. The proof combines splitting off and sampling with a bound on the size of nested families of vertex sets.

Abstract: Existing knowledge-base-assisted semantic communication schemes commonly adopt either single knowledge-base quantization (SKBQ) or multi-knowledge-base residual quantization (MKBQ). SKBQ incurs limited storage overhead but has restricted quantization capacity, whereas MKBQ supports progressive refinement by assigning an independent knowledge base (KB) to each stage, causing the KB storage to grow linearly with the transmission depth. To address this problem, we propose storage-scalable knowledge-base reuse quantization (SSKBQ), which reuses a compact set of KBs across multiple residual refinement stages and thereby decouples the number of transmission stages from the number of maintained KBs. A stage-aware residual supervision mechanism is further introduced to regularize intermediate quantized representations and encourage progressive refinement. Experimental results demonstrate that KB reuse provides an effective solution to the storage scalability problem while maintaining competitive progressive reconstruction performance.

Abstract: For a graph $H$, the $H$-freeness edge-deletion problem is the algorithmic problem of finding, for an input graph $G$, the minimum number of edges of $G$ whose deletion turns $G$ into an $H$-free graph. We show that for every graph $H$ containing a cycle, this problem is NP-hard. This proves a conjecture of Gishboliner, Levanzov and Shapira, and completes the characterization of the complexity of the $H$-freeness edge-deletion problem, answering a question of Alon, Shapira and Sudakov.

Abstract: Local similarity indices are widely used in link prediction on complex networks owing to their low computational cost; however, in sparse networks they assign a zero score to every node pair lacking common neighbors, which severely limits their predictive power. A natural remedy is to fuse node centrality indices with local similarity indices: the former provide global importance for the node pair, while the latter capture fine-grained local topology, and the two can be combined into complementary scores within a unified framework. This paper uses PageRank and DomiRank as two representative centrality measures and constructs a centrality--local-similarity fusion framework. The PageRank-based fusion proposed by Charikhi is first generalized to seven classical local similarity indices, and the universality of its improvement is systematically verified on nine real-world network datasets. Furthermore, the DomiRank centrality is introduced to build the DR-MD series of fused indices under a unified weighting coefficient, which overcomes the drawback that the PageRank-based fusion requires index-by-index weight tuning. Results of five-fold cross-validation together with Wilcoxon signed-rank tests show that, under the unified experimental protocol, all DR-MD indices consistently outperform the corresponding local baselines and their PR-MD counterparts on all nine datasets ($p=0.002$), and that the improvements remain robust against perturbations of $σ$ and the weighting coefficients within the near-critical parameter plateau; in particular, DR-RA achieves an average AUC of 0.7084, surpassing global methods such as Katz and RWR as well as several advanced similarity indices. The framework is inherently extensible, and its fusion paradigm can be straightforwardly generalized to couple other node centrality indices with local similarity indices.

Abstract: Let $X$ be a finite set with $|X|=n$ and let $\mathrm{Jac}(a,b)=|a\,\triangle\, b|/|a\cup b|$ be the Jaccard distance on the power set $2^X$. Lladser and Paradise recently proved that the metric dimension of $(2^X,\mathrm{Jac})$ is $Θ(n/\ln n)$, with the constant left open; their bounds are $(\ln 2)\,n/\ln n\lesssim β(2^X,\mathrm{Jac})\lesssim 2\ln(2e)\,n/\ln n$. We determine the constant: \[ β(2^X,\mathrm{Jac})=\frac{2n}{\log_2 n}\,(1+o(1))=(2\ln 2)\,\frac{n}{\ln n}\,(1+o(1)). \] The proof identifies the problem, on each ``slice'' of subsets of fixed cardinality, with the Erdős--Rényi coin-weighing problem for a spring scale (the problem of \emph{detecting matrices}). The lower bound is the Erdős--Rényi entropy argument applied to the middle slice; the upper bound follows from the explicit detecting families of Lindström and of Cantor and Mills, augmented by a single extra landmark that reveals cardinality.

Abstract: For an undirected graph $G = (V,E)$ and a fault bound $f$, an edge-fault-tolerant connectivity labeling scheme assigns short labels to vertices and edges, so that for any vertex pair $(s,t)$ and failed edge set $F\subseteq E$ with $|F|\leq f$, the connectivity between $s$ and $t$ in $G-F$ can be answered by inspecting only the labels of $s$, $t$ and edges in $F$. In this paper, we present a labeling scheme that uses $O(\log^{2}n)$-bit labels that can be computed in deterministic polynomial time. This improves upon the previous $\tilde{O}(\sqrt{f})$ deterministic bound of [Long, Pettie, Saranurak'25], and even slightly improves the $O(\min\{f+\log n,\log^{2}n\log f\})$ randomized bound of [Dory, Parter'21] and [Long, Pettie, Saranurak'25] when $f = Ω(\log^{2}n)$. Moreover, for a general $f$, this is the first labeling scheme that produces an $\tilde{O}(1)$-size labeling which is simultaneously correct across all queries. Our approach combines the cycle-space-based labeling scheme from Dory and Parter with a recent result by [Knauer'26] on sparse cycle bases.

Abstract: Higher-order structures offer a natural representation of complex systems that involve interactions between groups of different sizes. A widespread feature of their higher-order structure is nestedness, whereby interactions involving smaller groups are contained within larger ones. Yet, why interactions of different orders organise into nested structures remains largely unexplained. Here, we introduce an analytically tractable geometric model of higher-order networks in which a single latent geometric space couples interactions across orders, leading to the spontaneous emergence of nestedness. We show analytically and numerically that nestedness undergoes a transition between a nested geometric regime, where it remains finite in the thermodynamic limit, and a regime where it vanishes with system size. In this regime, we uncover a weakly geometric range characterized by an anomalously slow finite-size decay, allowing substantial nestedness to persist in finite systems even when its asymptotic value vanishes. Finally, with a single geometric coupling parameter, the model reproduces the nestedness profiles observed in real-world hypergraphs across different domains. Our results reveal latent geometry as a simple organising principle underlying the nested organisation of higher-order interactions.

Abstract: Given a graph $G=(V,E)$, let $S$ ($\subseteq V$) be a set of vertices. Two vertices are \emph{mutually visible} if there exists a shortest path in $G$ between them that does not contain any other vertex of $S$. A set $S$ is a \emph{Mutual Visibility Set} (\MVS) if every pair of vertices in $S$ is mutually visible. The concept of \MVS s in graphs has attracted significant attention since its introduction, as it provides an important structural property of graphs. However, determining a maximum \MVS\ in general graphs is computationally intractable; the decision problem of whether a graph admits an \MVS\ of size at least $k$ has been shown to be \emph{NP-complete}. Thus, prior work has focused on finding maximal \MVS s or restricting attention to specific graph classes. Cactus graphs form a fundamental low-treewidth class, yet the maximum \MVS\ problem for this class remains open. In this paper, we first determine the size of maximum \MVS~in cactus graphs, and introduce two self-stabilizing algorithms that construct such sets. The first algorithm uses a single BFS tree and stabilizes in $O(D)$ rounds with $O(\log n)$ bits per process on average; the second one uses parallel BFS trees and stabilizes in $O(|C_{\max}|+|T_{\max}|)$ rounds, which we show to be asymptotically tight as a function of these two parameters, even on graphs where $|C_{\max}|+|T_{\max}| = o(D)$.