Papers for

network protocol developers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Physical risk aware agents improve communication reliability in vehicle networks

Physical-Risk-Aware Decentralized Agents for Constrained Vehicle Communications

Abstract: Decentralized V2X resource control is challenging because each vehicle has only local observations, while reliability depends on network-wide interactions. We develop a physical-risk-aware spatio-temporal graph attention (PA-STGAT) framework for agentic V2X control. Each vehicle perceives its local interaction graph, retains short-term temporal context, and independently selects its PC5 resource and power. Network outcomes are used during centralized training to refine the shared policy. Transmitter-specific credits map reliability failures to individual vehicles. A dual-priced graph term further converts network violations into coordination signals for discrete resource selection, with higher priority on short time-to-collision links. Experiments show higher raw-policy reliability than the tested graph-based baselines. Under filtered execution, PA-STGAT meets the nominal empirical communication requirements across all five seeds, with tradeoffs among utility, delivery reliability, resource occupancy, and filter-induced repair. Compared with GNN+MATD3, it requires fewer resource repairs but achieves lower utility and mean delivery reliability. Mechanism ablations show that removing dual-priced graph coordination causes resource-selection collapse. Density and mobility tests characterize the operating limits of empirical constraint satisfaction.

Thu 12 NovMultiagent Systems
The gist
Vehicles in a network need to talk to each other, but each vehicle only knows what it can see nearby. This limited view can make communication unreliable across the whole network. The authors created a system where each vehicle uses local information and a shared policy learned from training to pick communication resources carefully, prioritizing safety-related messages. Their method, called PA-STGAT, helps maintain reliable communication even in tricky traffic situations, balancing safety, network use, and message delivery. Tests show it works better than some other approaches but has tradeoffs in how often repairs to the network are needed.
Open → 2611.17456v1

Planar graphs get smaller adjacency labels for faster connections

Tight B-Trees for Adjacency Labeling

Abstract: We show that planar graphs admit adjacency labels of size $\log n+O(\log\log n)$: every vertex gets a label of this many bits, and the adjacency of two vertices is decided from their labels alone, in constant time. This improves the $\log n+O(\sqrt{\log n\log\log n})$ of Dujmović et al. (J. ACM 2021) and the $\log n+O(\sqrt{\log n})$ of Gawrychowski and Janczewski (SOSA 2022). Equivalently, $n$-vertex planar graphs have an induced-universal graph with $n(\log n)^{O(1)}$ vertices, down from $n2^{O(\sqrt{\log n})}$. The same holds for graphs of bounded genus, apex-minor-free graphs and $k$-planar graphs. For every proper minor-closed class we get $\log n+O(\sqrt{\log n\log\log n})$, down from the $\log n+O((\log n)^{3/4})$ of Dujmović et al. (2026). Both results come from tight B-trees: nodes are split into parts of nearly equal size, so every node but the topmost stays within a factor $1\pm O(1/\log n)$ of its target size, and a root-to-leaf path loses only $O(\log\log n)$ bits.

Sun 8 NovData Structures and AlgorithmsDiscrete Mathematics
The gist
The paper improves how we assign short codes (labels) to points in certain types of networks called planar graphs, so that by looking only at these codes, we can instantly tell if two points are connected. The authors made these codes even shorter than before, saving space and making the check more efficient. This also helps represent these networks inside larger, universal maps that are more compact. Their technique applies not just to planar graphs, but also to other related kinds of networks, making it broadly useful.
Open → 2611.11444v1

Set reconciliation achieves minimal data overhead with fast updates and decoding

Linear Set Reconciliation with $O(d)$ Additive Redundancy

Abstract: In set reconciliation, two parties holding sets $A, B \subseteq [n]$ with $|A \triangle B| \le d$ seek to recover their symmetric difference from short $\mathbb{F}_2$-linear sketches, which is equivalent to recovering a $d$-sparse vector $x = \mathbf{1}_{A \triangle B} \in \mathbb{F}_2^n$ from its syndrome $Hx \in \mathbb{F}_2^m$. While the information-theoretic counting bound requires $L(n,d) := \log \sum_{i=0}^d \binom{n}{i} = d\log(n/d) + Θ(d)$ bits, existing polynomial-time schemes either use at least $d\lceil\log(n+1)\rceil$ bits (algebraic sketches, leaving an $Ω(d\log d)$-bit gap) or incur a multiplicative $(1+δ)L(n,d)$ overhead (peeling-based sketches), raising the question of whether $L(n,d) + O(d)$ bits is achievable with fast updates and decoding. We construct a public-coin randomized $\mathbb{F}_2$-linear sketch of length $L(n,d) + O(d) + λ\log^{O(1)} n$ that recovers each fixed input of weight at most $d$ with probability at least $1 - 2^{-λ}$, with $\log^{O(1)} n$ update time and $d\exp(O((\log\log n)^2)) = dn^{o(1)}$ worst-case decoding time. In particular, for $n \le 2^{\operatorname{polylog}(d)}$ and $λ\le d^{1-Ω(1)}$, this achieves $L(n,d) + O(d)$ bits with $\operatorname{polylog}(d)$ update time and $d^{1+o(1)}$ decoding time. Our construction encodes $d$ permuted rows via randomly scaled Pinsketch syndromes and sketches the resulting bit array column by column. Decoding columns sequentially from prefix predictions cancels recovered rows and exposes undecided rows as decoder-side hints, reducing each column to a hinted sparse recovery problem that we solve via a recursive sketch, HintSketch.

Sun 8 NovData Structures and AlgorithmsInformation Theory
The gist
Set reconciliation is about two parties quickly finding what items they don’t share between their collections without sending all their data. The authors found a way to represent these differences using a very close to the smallest possible number of bits, while still allowing quick updates and fairly fast decoding. They used clever linear algebra and a new method to gradually recover missing parts step-by-step. This method works well for large sets and small differences, making the process more efficient.
Open → 2611.11409v1

Efficient synchronization method cuts errors in distributed decision making

An Efficient Synchronization Scheme for Distributed Bandits

Abstract: We study the problem of synchronizing two players in a \emph{distributed multi-armed bandit} setting. The probability of \emph{synchronization error} is analyzed by recasting synchronization as a \emph{communication problem}. Using a well-designed random coding ensemble, we derive error exponents for the maximum-likelihood decoder. We then introduce a \emph{universal decoder} that achieves the same error exponents as the optimal decoder. Finally, applying these results to distributed multi-armed bandits, we show an upper bound on the regret of our synchronization scheme.

Fri 6 NovInformation Theory
The gist
When two decision makers work separately but want to stay coordinated, errors can happen because they don’t communicate perfectly. The authors treat this coordination problem like sending messages over a noisy channel and design a way to reduce mistakes. They provide mathematical guarantees on how fast errors drop with their approach. Their method also helps keep the overall decision quality high when working with multiple options.
Open → 2611.09806v1

New mathematical bounds improve spherical code design and energy limits

Levenshtein-type bounds for $(a,b)$-avoiding spherical codes

Abstract: We develop a Levenshtein-type linear programming framework (for maximal $s$-codes and for minimal energy) for $(a,b)$-avoiding spherical codes, that is, codes whose inner products between distinct points avoid $(a,b)$. We introduce and investigate signed measures that are positive definite up to an appropriate degree and yield stationary auxiliary linear programming polynomials and exact quadrature formulas. We give explicit conditions for positivity of the quadrature weights and sufficient Krein-type conditions for nonnegative Gegenbauer coefficients (positive definiteness of the candidate optimal linear programming polynomials). Under these hypotheses and suitable node-location assumptions, the resulting cardinality bounds are optimal within the corresponding degree restriction and unique under natural nondegeneracy conditions. Under proper conditions on the quadrature nodes, we obtain universal lower energy bounds by utilizing Hermite interpolants as polynomial solutions of the respective linear program. Common test functions characterize optimality in the full polynomial linear programs under mild additional assumptions.

Thu 5 NovInformation Theory
The gist
The paper studies spherical codes, which are sets of points on a sphere with certain spacing properties. The authors develop new mathematical tools to find the largest possible number of points that avoid specific inner product ranges between them. They also establish lower bounds on the minimum energy configurations of these points. Their approach uses and extends linear programming techniques and special polynomials, allowing for precise and sometimes unique optimal solutions under certain conditions.
Open → 2611.08709v1

General formulas define capacity for quantum multi-sender channels

Information-Spectrum General Formulas for the Capacity Region of Classical-Quantum Multiple Access Channels

Abstract: For classical-quantum multiple access channels (cq-MACs) with two senders, we give several general expressions for the capacity region, valid for arbitrary sequences of channels. In the case of asymptotically vanishing error ($\varepsilon=0$), the capacity region is expressed in terms of spectral inf-mutual information rates. For every $0\le\varepsilon<1$, the $\varepsilon$-capacity region is expressed in terms of a quantity defined through a linear combination of three alternative hypotheses. In particular, the outer bound of Kubo and Nagaoka (2015) is tight. Our results include the quantum counterpart of the general formula of Han (1998) for the classical MAC. The most important ingredient is the one-shot inner bound of Sen (2021), which we apply to each member of an arbitrary channel sequence.

Thu 5 NovInformation Theory
The gist
Communicating information over quantum channels with more than one sender is tricky because quantum effects change how data can be combined and sent reliably. The paper gives formulas that describe exactly how much information two senders can send over a quantum channel while keeping error low. These formulas work for any kind of channel sequence and extend earlier classical results into the quantum world. This helps understand the limits of quantum communication when multiple messages are sent together.
Open → 2611.07462v1

Streaming space understanding for Boolean constraint problems with deletions

A New Characterization of Streaming Decidability of Boolean CSPs Under Deletions

Abstract: We characterize the single-pass streaming space complexity of Boolean CSP satisfiability in the strict-turnstile model for every fixed constraint language $Γ$ of $k$-ary Boolean relations that is not trivially satisfiable. Constraints can be inserted or deleted with nonnegative multiplicities; satisfiability is decided for those remaining at the end. While Sharma and Velusamy [ESA 2026] characterized insertion-only complexity via non-redundancy (up to logarithmic factors), we show that strict-turnstile complexity is governed by the integer capturing degree. For $R\subseteq\{0,1\}^k$, let $d_R$ be the minimum degree of an integer-coefficient polynomial vanishing exactly on $R$ over the Boolean hypercube, and set $d_Γ=\max_{R\inΓ}d_R$. On polynomial-length streams, we obtain an $O_k(n^{d_Γ}\operatorname{polylog} n)$-space randomized algorithm and an $Ω_k(n^{d_Γ}/\log n)$ lower bound for all algorithms. Moreover, our algorithm outputs a sparse instance preserving every satisfying assignment. This yields, to our knowledge, the first insertion-only versus turnstile separation for streaming CSPs. It also differs from the Fourier-degree characterization of exact optimization by Kol, Paramonov, Saxena, and Yu [ITCS 2023]. For $k\ge3$, $k$-XOR with literals has three distinct space complexities: $\widetildeΘ(n)$ for insertion-only satisfiability, $\widetildeΘ(n^{\lceil k/2\rceil})$ for strict-turnstile satisfiability, and $\widetildeΘ(n^k)$ for exact optimization in either model.

Thu 5 NovComputational Complexity
The gist
This work studies how much memory is needed to decide if certain logic-based puzzles, involving variables that can be true or false, can be solved when the puzzles are given as a long sequence of steps that add or remove conditions. The authors give a precise rule, based on a mathematical property related to polynomials, that tells how this memory need grows with the puzzle size. They also show the difference between only adding conditions and allowing both adding and removing, with the latter requiring more memory. This helps explain the complexity of solving these puzzles in real-time scenarios with changing data.
Open → 2611.07309v1

Steiner shortcuts in graphs require large diameters with few edges

Polynomial Lower Bounds for Steiner Shortcuts via Test Functions

Abstract: The Steiner shortcut problem asks whether every directed graph $G=(V,E)$ with $n$ vertices and $m$ edges admits an augmentation $G_{+}=(V\cup V_{+},E\cup E_{+})$ with $m^{1+o(1)}$ edges such that $G_+$ has the same reachability structure as $G$ (i.e. for all $s,t\in V$, $s$ reaches $t$ in $G$ iff $s$ reaches $t$ in $G_+$), and the diameter of $G_{+}$ is $m^{o(1)}$. This is a core combinatorial question underlying many reachability algorithms in the dynamic, streaming, and CONGEST models, and all parallel algorithms with almost-linear work and sublinear depth. A sequence of works ruled out such a shortcut $G_{+}$ in the non-Steiner setting where $V_{+}=\emptyset$. However, as recently shown by Bernstein et al. [STOC '26], all known non-Steiner lower-bound constructions fail once Steiner vertices $V_{+}$ are allowed. This paper rules out almost-optimal Steiner shortcuts: we show an infinite family of graphs $G=(V,E)$ with the property that, for any $\varepsilon>0$, a Steiner shortcut $G_{+}=(V\cup V_{+},E\cup E_{+})$ with $m^{1+\varepsilon}$ edges must have diameter at least $n^{1/56-O(\varepsilon)}$. Our construction strengthens the standard non-Steiner lower-bound framework via an additional structure that allows Steiner vertices to be replaced by original vertices; we can then reduce back to the standard arguments without Steiner vertices. This new structure is achieved via a new general strategy based on test functions, which is quite flexible and can potentially be extended to applications beyond our work. We also generalize our lower bound to exact Steiner hopsets in undirected graphs and to depth reduction for monotone circuits. The latter significantly strengthens the classical lower bound based on Sylvester matrices.

Wed 4 NovData Structures and Algorithms
The gist
The paper studies a question about simplifying complex networks while keeping their essential connections. It asks whether adding new points and connections can make the network much easier to navigate without losing any paths between original points. The authors show that even when adding extra points (called Steiner vertices), it's still impossible to make the network much simpler without making some paths very long. They developed a new mathematical method called test functions to prove this, which might be useful in other problems too.
Open → 2611.07043v1

Individual sequence limits on error rates for adaptable communication channels

Fano's Inequality and Channel Capacity in the Individual-Sequence Regime

Abstract: We derive an individual-sequence analogue of Fano's inequality, replacing entropy by Lempel--Ziv (LZ) complexity and probability of error by empirical error frequency. In the setting considered, an arbitrary encoder maps a message to a channel input sequence $\{x_t\}$, the channel maps the input to an output $\{y_t\}$ in a completely arbitrary manner, and a block finite-state decoder produces an estimate of the channel input from the output. The individual-sequence Fano inequality lower-bounds the empirical symbol-error frequency in terms of the LZ complexity of the channel input conditioned on the channel output. This leads to a channel coding converse: reliable communication at a given rate is possible only if that rate does not exceed the individual-sequence LZ channel capacity, defined as the LZ mutual information maximized over channel inputs and minimized (worst-case) over a noise set. We also prove a matching achievability theorem for the class of \emph{symbol-wise invertible} channels, in which the channel output at each time $t$ is $y_t = f(x_t, v_t)$, $v_t$ being a `noise' variable, and $f(\cdot,v)$ is a bijection for every fixed $v$. This class includes group-additive channels $y_t = x_t \oplus v_t$ studied by Feder and coworkers. For such a channel, any rate below the LZ capacity is achievable with vanishing per-message error frequency, simultaneously for every $v^n$ in a given noise set $\mathcal{N}$, provided $\mathcal{N}$ is closed under block permutations; this condition is satisfied by any noise set that depends on $v^n$ only via its type class with respect to such blocks. The achievability uses a universal decoder that requires no knowledge of the channel and no feedback.

Wed 4 NovInformation Theory
The gist
This paper looks at how well data can be sent through a communication channel that might behave in any unpredictable way. The authors created a new version of a classic information theory rule (Fano's inequality) that uses a specific measure of sequence complexity instead of randomness. They show that if you want to send information reliably, the rate must not exceed a new defined capacity based on this complexity. For a certain kind of channel where output changes predictably with input and noise, they prove you can achieve this capacity without knowing the channel details in advance.
Open → 2611.06182v1

Theory for designing rules to manage identical autonomous agent systems

Towards a Theory for the Design of Rules in Multi-Agent Systems: the case of Homogeneous Fleets

Abstract: The regulation of systems composed of many interacting decentralised agents is a long-standing problem. This problem has typically been resolved by the imposition of rules. Rules resolve the limitations of sub-optimal agents whilst simultaneously aligning the behaviour of the agents with the demands of society. Traffic laws, for example, let a driver cross a junction without seeing around the corner, and transport protocols such as TCP let applications share a network without knowing of one another. The problem is more pressing today, as autonomous systems are deployed in society. In this work, we establish the basis of a system-agnostic theory of rule design for multi-agent systems. We first state the rule design problem (RDP) in its generality. It relates a rule to the set of system performances, defined by the regulator, that the agents deployed under it can attain. However, it is not yet possible to solve the RDP in full generality. As such, we introduce the homogeneous rule design problem (HRDP), in which the agents in each environment are identical, and among other interesting properties, show that under worst-case aggregation the two problems have the same solution, bypassing the combinatorial complexity of the RDP. To solve the RDP under worst-case aggregation we propose Rule Branch and Bound (RuleBnB), an anytime branch-and-bound algorithm. Finally, we illustrate the value of solving the RDP on an autonomous driving case study.

Sun 1 NovMultiagent Systems
The gist
Managing many automated agents that interact can be tricky, especially when trying to make sure they behave well together. The authors study how to design rules that guide groups of identical agents to achieve good overall system outcomes. They present a simpler version of the problem that can be solved more easily and propose an algorithm called Rule Branch and Bound for finding these best rules. They also show how this approach can help manage autonomous cars safely in traffic.
Open → 2611.02260v1

Quantitative methods improve reachability estimates in probabilistic infinite systems

Quantitative Reachability Properties Beyond Decisiveness

Abstract: Decisiveness is central to reachability algorithms for infinite Markov chains, but is a qualitative notion: it guarantees that path-enumeration algorithms terminate, without an a priori bound on the horizon. We study decisiveness quantitatively of Markov chains, and apply our results to the approximate quantitative coverability problem for effective probabilistic well-structured transition systems (pWSTS). We introduce truncation sets, which represent the horizons sufficient to approximate the reachability probability within a precision $\varepsilon$. These sets reformulate decisiveness quantitatively, and their elements can be computed when it is decisive. To obtain such horizons, before any exploration, we introduce geometrically reachable sets, for which the probability of not reaching them within n steps decreases exponentially in n, up to a prefactor depending on the initial state. Horizons valid for all initial states exist iff this prefactor can be chosen uniformly for boundedly coarse chains. For such pWSTS, including probabilistic vector addition systems and Galton-Watson processes, we obtain a priori global horizons growing at most logarithmically in $1/\varepsilon$. In the non-uniform case, we give a drift condition ensuring the existence of a finite geometrically reachable set. Under this condition, we derive a priori horizons growing at most logarithmically in $1/\varepsilon$ and in the weight w(x) measuring the size of the initial state x. In both cases, we compute a horizon function whose evaluation on any initial state and precision requires only a constant number of elementary operations $(+, -, \times, / \text{ and } \log)$. For probabilistic lossy channel systems, this yields, to our knowledge, the first explicit a priori horizons from arbitrary initial states, and it extends to $ν$-pLCS, a new infinitely branching variant with probabilistic emissions.

Mon 26 OctLogic in Computer ScienceFormal Languages and Automata Theory
The gist
Figuring out the chance of reaching a specific state in some infinite random systems can be very hard, especially when you don't know how far to look ahead. The authors study ways to estimate these chances more precisely by introducing new tools called truncation sets and geometrically reachable sets, which help decide a sufficient horizon to approximate probabilities within a certain precision. Their approach gives a way to calculate how far you need to explore in these systems to get good numeric estimates, even before starting the computation. They also provide formulas for this horizon that only require simple calculations and apply it to various probabilistic infinite models.
Open → 2610.35308v1

Stochastic push-pull may lose speedup on changing network connections

On the Limits of Stochastic Push-Pull over Time-Varying Digraphs

Abstract: Stochastic Push-Pull achieves linear speedup with respect to the network size $n$ on static strongly connected digraphs, but whether this speedup persists on time-varying networks remains unclear. In this work, we construct a quadratic decentralized problem on period-two networks showing that stochastic Push-Pull may fail to attain linear speedup over time-varying digraphs. For $p$-periodic networks, we identify an effective node count $n_{\mathrm{eff}}\le n$ that governs the leading stochastic term. Specifically, for smooth nonconvex objectives, we establish convergence upper bounds and matching lower bounds for stochastic Push-Pull with constant stepsizes, both exhibiting the leading-order dependence $Θ(1/\sqrt{n_{\mathrm{eff}} T})$. When $p=1$, the identity $n_{\mathrm{eff}}=n$ recovers the usual linear speedup for static digraphs. However, periodic networks can have $n_{\mathrm{eff}}=o(n)$, demonstrating the loss of linear speedup under temporal variation. Numerical experiments illustrate effective-count scaling and the separation between static and periodic networks, consistent with our theoretical findings.

Fri 23 OctMachine Learning
The gist
Stochastic Push-Pull is a method that speeds up tasks shared across networked computers. It works well and gets faster as more computers join, but usually only when their connections don’t change. The authors show that when the network’s connections change periodically, this speedup can be much less, meaning the method doesn’t scale as well. They identify a smaller effective number of nodes that truly impact performance and confirm this with experiments.
Open → 2610.32422v1

Telecom network security improved with multi-stage attack analysis framework

MASAR: Multi-stage Attack Surface Analysis and Reasoning Framework for Telecom Networks

Abstract: The increasing complexity of modern telecommunications networks introduces security challenges that require systematic threat analysis. However, a gap remains between architectural threat modeling frameworks, such as Spoofing, Tampering, Repudiation, Information Disclosure, Denial of Service, and Elevation of Privilege (STRIDE), and operational knowledge bases, such as the MITRE Five-G Hierarchy of Threats (FiGHT). This gap limits the ability to connect architectural weaknesses with specific protocol behaviors and attack sequences. This paper presents Multi-stage Attack Surface Analysis and Reasoning (MASAR), a formal framework that bridges this gap through three layers: strategic threat mapping, logical attack path decomposition using directed acyclic graphs (DAGs), and operational synthesis of tactics, techniques, and procedures (TTPs). MASAR is evaluated using a 5G-ready IP Multimedia Subsystem (IMS) architecture, examining two signaling attack scenarios: early media billing bypass through Session Initiation Protocol (SIP) signaling and subscriber information disclosure and topology discovery through the Diameter Cx interface. MiniZinc constraint models are used to analyze the reachability of unsafe protocol states. The analysis demonstrates how MASAR connects architectural threats with specific protocol behaviors and supports security controls that account for network states in telecommunications systems.

Wed 21 OctCryptography and SecurityNetworking and Internet Architecture
The gist
Modern telecom networks are complex and face many security risks that are hard to understand fully. The authors created a new system called MASAR that links theoretical security weaknesses with real-world network actions and attack steps. MASAR uses diagrams and formal models to break down how attacks happen and tests these ideas on 5G network components. This approach helps security teams better predict and block attacks based on detailed telecom protocols and network states.
Open → 2610.29343v1

Dynamic algorithm keeps bipartite graphs 3-colored with minimal changes

Dynamic 3-Coloring of Bipartite Graphs with Optimal Locality

Abstract: We give a dynamic graph algorithm which maintains a 3-coloring in bipartite graphs under edge insertions such that the coloring only changes within a radius of $O(\log n)$ around an inserted edge. In the context of locality theory in distributed graph algorithms, this gives an upper bound on the locality under the dynamic-LOCAL model. Our bound on the locality is tight, as the problem admits a matching $Ω(\log n)$ lower bound in the stronger online-LOCAL model, by a result of Chang et al. [PODC 2024]. Thus, our result closes the gap between dynamic and online locality of this problem.

Wed 14 OctData Structures and AlgorithmsDistributed, Parallel, and Cluster Computing
The gist
Coloring a graph means assigning colors to its points so that connected points have different colors. The authors developed a method that updates the coloring of bipartite graphs efficiently when connections (edges) are added, changing colors only nearby the new edge. Their approach limits color adjustments to within a small, logarithmic distance, which is the best possible under known theoretical limits. This result helps understand how quickly and locally such updates can happen in distributed computing systems.
Open → 2610.19710v1

Laser method improves detecting complex protocol dependencies accurately

LASER: Defeasible Certificate Search for Long-Range Protocol Dependencies

Abstract: Protocol specifications rarely justify executable behavior in one place: a transition may inherit its source state from a remote control block, name its events only by number, and remain subject to a later correction. Recovering the nearby clause is therefore insufficient; the system must assemble a source-linked certificate and determine whether any stronger rule applies. We introduce LASER, a proof-carrying search method for sparse, defeasible protocol evidence. LASER represents missing support and unresolved corrections as explicit obligations, searches typed evidence routes, and lets an occurrence-aware symbolic checker alone decide whether a certificate warrants, refutes, or leaves a behavior unresolved. On 91 BehaviorCheck families under a matched 2K budget, LASER improves Joint Edge+Proof over the strongest local reader on two model families ($Δ=+.132$, $p=.017$; $Δ=+.198$, $p<.001$) while cutting false discoveries by 2--3$\times$. Controlled replays attribute the gain and its limits: neither reference routing nor deterministic citation expansion alone exceeds the local baseline; whole-document reading (29--65K tokens), two-round iterative retrieval, and even oracle minimal-certificate evidence all fail to reach LASER, localizing the bottleneck in typed obligation closure rather than evidence access. An authority-corruption replay shows source-link errors only cause abstention, while the only unsafe-warrant mechanism is mis-recording a Held erratum as Verified, confined to that erratum's family. LASER thus improves long-range dependency recovery while converting incomplete evidence and uncertain authority into explicit residual obligations rather than unsupported behavior.

Sat 10 OctSoftware EngineeringArtificial Intelligence
The gist
Protocols that control how computers talk often spread their rules across many places, making it hard to understand what exactly should happen. The authors present LASER, a method that gathers pieces of evidence from far apart parts of a protocol and decides if a behavior is allowed, blocked, or unclear. Unlike other approaches that just look nearby or read the whole document blindly, LASER carefully tracks missing or conflicting information and flags uncertainty explicitly. Tests show LASER finds more correct protocol behaviors and avoids false positives better than previous tools.
Open → 2610.14552v1

Improved bounds on consensus speeds for vectors in dynamic networks

New Contraction Bounds for Multidimensional Asymptotic Consensus in Dynamic Networks

Abstract: This work studies the multidimensional asymptotic agreement problem in dynamic networks. We assume that nodes have $d$-dimensional inputs and need to converge arbitrarily close to each other's inputs while their vectors stay inside the convex hull of all inputs. We present a new upper bound of $\sqrt{2d/(3d+1)}$ on the contraction rate of asymptotic agreement in the non-split network model, where $d$ is the dimension of the input and $\sqrt{2d/(3d+1)}\rightarrow \sqrt{2/3}\approx 0.816$ for $d\rightarrow\infty$. To this end, we adapt the BallMidpoint algorithm (Melnyk, 2026) recently introduced for the all-to-all communication model. This algorithm lets the nodes choose the midpoint of the smallest enclosing ball of the received vectors. This bound is strictly worse than the $\sqrt{1/2}\approx 0.707$ contraction rate for fault-tolerant approximate agreement in all-to-all communication networks because the convex hulls of the nodes do not have a common intersection, and only intersect pairwise. Our bound improves over the previously best-known contraction rate of $\sqrt{7/8}\approx 0.935$ for dynamic networks via the MidExtremes algorithm (Függer and Nowak, 2018). We present the first multi-dimensional lower bound of $2/3$ for the contraction of coordinate-free memoryless anonymous deterministic algorithms in non-split networks, for $d\ge 8$. This result shows that the previously best-known lower bound of $1/2$ on the contraction rate for $n\ge 3$ and $d=1$ is not tight in higher dimensions. If $n$ is infinite, we extend this lower bound to $\sqrt{1/2\cdot d/(d+1)}$, which converges to $\sqrt{1/2}$ for $d\rightarrow \infty$. We further show that for a single round, the one-round contraction is at least $\sqrt{\frac{2d-2}{3d+7}}$, which converges to $\sqrt{2/3}$ for $d\rightarrow\infty$, showing that the BallMidpoint strategy is asymptotically optimal for one round.

Thu 8 OctDistributed, Parallel, and Cluster Computing
The gist
In networks where many devices or nodes try to agree on a shared value represented by multiple numbers, it’s challenging to reach agreement quickly and reliably. The paper studies how fast nodes can come close to each other’s values when those values are multi-dimensional vectors. The authors found a new tighter upper limit on how quickly agreement can improve under certain network conditions, and they also proved new lower limits showing how fast any method can possibly be. Their results help explain the best possible speed of consensus in complex network settings.
Open → 2610.11805v1

Regular languages can use simpler cycle-based automata graphs

Every Regular Language Has a Bipartite Cactus Automaton

Abstract: Thompson's classical construction turns every regular expression into an equivalent epsilon-NFA whose transition graph is series-parallel. The construction uses epsilon-transitions, and eliminating them by the usual shortcut construction need not preserve planarity or the bound of two on the treewidth of the transition graph. Book and Chandra proved that every regular language nevertheless has an epsilon-free NFA with a planar transition graph. We show that the transition graph can in fact be chosen to be a bipartite cactus: every cycle is even, and any two cycles have at most one vertex in common. In particular, it is outerplanar and has treewidth at most two. This is a considerably more simple structure than the general series-parallel guarantee supplied by Thompson's construction. The proof is a direct induction on parity-typed regular expressions and uses only elementary closure properties of cactus graphs.

Thu 8 OctFormal Languages and Automata Theory
The gist
Regular languages can be represented using machines called automata. Earlier, these machines were known to have complex graph structures. The authors found that every regular language can be represented with a simpler kind of graph called a bipartite cactus, where cycles are well-structured and the graph has nice mathematical properties. This makes understanding and working with these machines easier in some ways. Their proof uses basic properties of these cactus graphs and works by breaking down the language step-by-step.
Open → 2610.11717v1

Attention improves multi-agent communication in low bandwidth settings

Attention-based Hierarchical Variational Information Bottleneck for Robust Multi-Agent Communication under Variable Bandwidth

Abstract: Learning-based multi-agent communication under limited bandwidth does not only require deciding what to communicate, but also structuring messages so that partial transmissions remain useful. We study this problem under prefix truncation, where only the first part of each message is received. To address it, we propose \textbf{AH-VIB}, an attention-based autoregressive variational communication model that combines a variational information bottleneck (VIB) with sequential message generation and a hierarchical robustness loss. We evaluate AH-VIB on a custom cooperative object-inspection and occupancy-mapping task, where agents equipped with a limited field-of-view sensor coordinate to scan inspection objects in an occupancy-grid world, under variable and fixed bandwidth conditions, and compare it against MADDPG, CommNet, a flat VIB baseline, and an autoregressive MLP ablation. AH-VIB achieves competitive mean return while improving performance reliability under the most constrained bandwidth conditions. These results indicate that AH-VIB improves the reliability and graceful degradation of learned communication under bandwidth constraints.

Mon 28 SeptMachine LearningArtificial Intelligence
The gist
Communicating clearly between multiple agents is hard when only part of a message gets through. The authors study how to make messages that stay useful even if interrupted early. They propose a new method called AH-VIB that uses attention and a special compression technique to build messages piece by piece. Tested in a task where agents explore an environment with limited sensors, AH-VIB keeps communication reliable even when bandwidth is very limited, doing better than existing methods. This helps agents share useful info even when their messages get cut off.
Open → 2609.34860v1

Hybrid key establishment secures session keys with downgrade protection

Transcript-Bound Combiners for Downgrade-Resilient Hybrid Post-Quantum Key Establishment: Definition, Proof, and Embedded-Device Cost

Abstract: Hybrid key establishment runs a post-quantum key-encapsulation mechanism (KEM) alongside a classical Diffie-Hellman primitive, so that the session key stays secure while either component resists attack. This design is now standardized in the Transport Layer Security protocol, Secure Shell, and the Internet Key Exchange, with the standardized module-lattice KEM (ML-KEM) as the post-quantum component. A hybrid KEM secures the derived key, but not the integrity of the negotiation that selects which primitives are used. Full protocols authenticate that negotiation through a handshake transcript; a hybrid KEM deployed as a standalone drop-in primitive, or inside a minimal handshake without transcript authentication, inherits no such guarantee, and an active attacker can strip the post-quantum option. We ask what the key schedule alone must contain to make downgrade resilience a local property of the combiner. We give a game-based definition at the combiner layer and prove a two-sided separation: a combiner that ignores the transcript is downgraded with certainty, whereas one that binds the session key and the confirmation tag to a hash of the transcript blocks every such attempt, up to a term negligible for a 256-bit transcript hash. We also give an explicit strongest-link security bound. Using a calibrated cost model composed from published Cortex-M4 measurements, transcript binding adds one hash per party - about 11.8% of handshake computation but only 1.5% of radio-inclusive energy - and adds no messages or bytes on the wire. Every reported number is produced by a released harness that passes a 30-check validation gate.

Fri 18 SeptCryptography and Security
The gist
Hybrid key establishment combines old and new encryption methods to keep session keys safe, even if one method is broken. The authors found that if the process doesn’t check the entire conversation (transcript), attackers can remove the new, quantum-proof encryption option. They show that including a hash of the transcript in the key generation stops this attack with very high confidence. Their approach adds a small computational cost but no extra messages, making it practical for devices like embedded systems.
Open → 2609.21273v1

Channel aware folding cuts data traffic in distributed systems

Channel-Aware Selection of Folded Bloom Filters for Distributed Systems

Abstract: Periodic Bloom-filter transmission can impose substantial overhead in communication-constrained distributed systems. Lossless compression preserves membership behavior but provides a single transmission size, whereas established OR folding produces smaller representations with higher false-positive rates (FPRs) while preserving the no-false-negative property. This paper investigates channel-aware selection among OR-folded representations. The sender retains an unchanged canonical filter, constructs a catalog satisfying a maximum FPR, and selects the FPR-qualified representation with the largest retained length supported by the communication resources available at each reporting opportunity. Unlike folding driven principally by cardinality and false-positive constraints, selection is driven by time-varying communication conditions. Using two phishing URL datasets, the framework is evaluated under Five-State Markov Capacity, Gilbert--Elliott burst-error, and Rayleigh block-fading models. Channel-aware folding improves communication efficiency and receiver freshness relative to complete-filter and lossless-compression baselines when communication opportunities vary substantially. Under the more favorable Gilbert--Elliott model, it remains competitive in efficiency while maintaining the freshest receiver state. These results show that FPR-qualified folded views provide useful transmission operating points when a recent lower-fidelity update is preferable to delaying a larger representation.

Sun 13 SeptInformation TheoryCryptography and SecurityNetworking and Internet Architecture
The gist
Sending large sets of data in distributed systems can use a lot of communication resources. The authors study special methods that shrink this data, called folded Bloom filters, which trade some accuracy for smaller size. They develop a way to choose the best-sized data version based on current network conditions, keeping the data fresh and reducing communication costs. Tests on phishing URL data and different network scenarios showed this approach can work better than traditional fixed-size or fully lossless methods.
Open → 2609.14458v1

LLMs struggle to accurately reason network protocol state machines

RFCLLM: Evaluating LLMs' Reasoning Ability of Network Protocol State Machines

Abstract: Mapping textual specifications into formal representations is essential for ensuring the correctness of protocol designs and implementations. LLM-generated mappings, used for networking security or testing, are assumed to capture a perfect understanding of the specification, which may not hold in practice. The goal of this paper is to assess the extent to which LLMs can interpret the specification correctly. We examine the degree to which an LLM's implicit representation of a finite-state transition system-defined via natural language descriptions-aligns with a manually generated ground-truth model. We designed 4 tasks and 1482 task queries for 16 protocols. We evaluated different judge biases, observed the inherent difficulty gaps between tasks, looked into the effect of 4 context types, and the influence of protocol characteristics. Our work contributes to a step toward verifying whether LLMs can really be trusted in FSM (Finite State Machine) reasoning of protocol specifications.

Fri 11 SeptComputation and Language
The gist
When designing network protocols, people write rules in plain language that need to be carefully translated into formal state machines to ensure they work correctly. This paper studies how well large language models (LLMs) can understand those plain language rules and represent them as state machines. The researchers found that LLMs often do not fully capture the precise behavior described in the specifications. They tested many tasks across different network protocols to better understand where and why LLMs make mistakes in reasoning about these state machines.
Open → 2609.13389v1