Papers for
network protocol designers
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.
Theory advances on subfield metric codes reveal structural and density insights
New Results on the Subfield Metric
Abstract: In this paper, we further develop the theory of the recently introduced $λ$-subfield metric. We investigate extremal codes, classical bounds and asymptotic densities in this setting. We first study codes attaining a Singleton-type bound, called Maximum $λ$-subfield Distance (M$λ$D) codes. We establish structural restrictions on their parameters and extend the theory to sublinear codes. We then investigate the asymptotic density of M$λ$D codes in several parameter regimes and compare their behavior with that of MDS and MRD codes. We then turn to a Plotkin-like bound, where we construct a family of constant-weight codes attaining the bound and classify all non-degenerate linear constant-weight codes for $λ>1$. Finally, we complement the collection of classical coding-theoretic bounds available for the $λ$-subfield metric by deriving Griesmer-, Elias- and Johnson-type bounds.
Exact mean and variance of stabilization time in self-stabilizing graph coloring
The Exact Stabilization Time of Self-Stabilizing Coloring: Mean, Variance, and Distribution
Abstract: The worst-case stabilization time of a self-stabilizing algorithm usually says little about its typical behavior beyond the order of magnitude. This paper revisits the classical self-stabilizing $Delta+1$ coloring algorithm with vertices activated at random, one at a time (the random central daemon). Considering the number of color changes as a random variable, we study its mean, variance and, on several families of graphs, its exact distribution. The analysis rests on a reduction: a vertex changes color, at most once, exactly when it is not a local maximum of a uniformly random labeling of the vertices, maxima being taken among the neighbors that share its initial color (the monochrome initial configuration is the slowest case). What can be predicted depends on what is known of the graph. The degree distribution (the view at distance one) gives the mean. The variance needs the view at distance two, in particular the triangles, and the full law needs the whole graph. We give closed-form results, from monochrome and from uniformly random initial configurations, on paths, cycles, random trees, Erdős-R{é}nyi graphs and bipartite random graphs. From a monochrome start, the mean stays within a factor two of the worst case, whereas the variance ranges from zero (disjoint cliques) to order $n^2$ (the star on $n$ vertices)..
Vehicle attack injection framework reveals traffic effects of falsified messages
Attack Injection to Vehicle Reactions: Extensible Closed-Loop Adversarial Evaluation Framework
Abstract: Autonomous vehicles can use information exchanged with other vehicles and roadside infrastructure to support driving decisions. However, applications that rely on this information can make unsafe decisions when it is falsified. Studying the resulting traffic effects requires following received information through application decisions, vehicle reactions, and subsequent interactions. We present an extensible closed-loop adversarial evaluation framework built on VaN3Twin, a platform for traffic and wireless network simulation, with a diverse attack library and a labelled dataset covering benign and attack conditions. A key advantage of the framework is that it can be extended with additional attacks, message paths, receiving applications, and logging fields. The added library contains 76 configurable attack profiles adapted to message formats defined by the European Telecommunications Standards Institute. These profiles are organized into nine groups of related attacks, referred to as suites. The framework connects live attack injection and simulated network delivery to receiving applications, whose selected commands update vehicle movement. The resulting state feeds subsequent message generation, closing the loop. The dataset links physical vehicle states and message exchanges to attack labels, application decisions, selected commands, and traffic outcomes. Evaluation with individual and combined attack suites confirmed execution of all profiles, and every suite produced requests linked to attacked messages. A recorded sequence also showed a vehicle reacting to an attacked message and subsequently influencing another vehicle through an unmodified message describing its updated movement. These findings demonstrate how live injection and vehicle feedback support the study of direct and indirect effects as traffic evolves.
New complexity bounds for reachability in special directed surface graphs
Path Isolation and Reachability in Surface-Embedded Graphs with Restricted Cycle and Cut Structure
Abstract: We study the reachability problem in directed surface-embedded graphs under two structural restrictions, using isolating weight assignments. First, we consider graphs whose underlying undirected embeddings contain at most polynomially many simple surface non-separating cycles. We develop a polynomially bounded, logspace-computable skew-symmetric edge-weight assignment with nonzero circulation around every simple cycle. This yields an unambiguous logspace (UL) upper bound for directed reachability. The construction also gives an SPL upper bound for bipartite perfect matching in the corresponding undirected graph class. Second, for $g$-genus directed graphs admitting a balanced hierarchical genus decomposition with $O(\log n)$ crossing edges at every partition, we obtain an unambiguous $O(\log g \cdot \log n)$-space bound for reachability. Our approach combines path-isolating weights for lower-genus subgraphs using polynomially bounded FKS hashing refinements at successive merging levels.
New limits on memory versus speed for dynamic graph connectivity
Connectivity in a New Bounded-Space Dynamic Model
Abstract: We introduce a new model for dynamic algorithms in which the algorithm has read-only oracle access to a dynamically changing input and random access to its own bounded workspace. It is a dynamic analogue of the time-space tradeoffs for static inputs studied in complexity theory, where only writable memory counts as space. We study dynamic undirected $s$-$t$ connectivity: after every edge update to an $n$-vertex graph, an algorithm with $S$ words of workspace must report whether $s$ and $t$ are connected. The graph is accessed via adjacency list queries (degree, $j$-th neighbor) or adjacency matrix queries. Our algorithms are randomized; our lower bounds hold for randomized algorithms with $cn$ bits of workspace, $c>0$ a small constant ($cn/\log n$ for the worst-case matrix bound). We prove: (1) With adjacency lists, worst-case time $\tildeΘ(n^2/S^2)$ per insertion is necessary and sufficient for incremental algorithms. (2) With an adjacency matrix, worst-case time $\tildeΩ(n^2/S)$ per insertion is necessary for incremental algorithms, and sufficient for $S\ge\sqrt{n}$. (3) With amortization, incremental algorithms achieve $\tilde O(n/S)$ time per insertion with adjacency lists and $\tilde O(n^2/S)$ with an adjacency matrix, while $\tildeΩ(\sqrt{n/S})$ and $\tildeΩ(n\sqrt{n/S})$, respectively, are necessary. (4) Fully dynamic algorithms need amortized time $\tildeΩ(n/S)$ per update with adjacency lists and $\tildeΩ(n^2/S)$ with an adjacency matrix, even on forests, where both bounds are tight (lists: under bounded degree). Conventional dynamic connectivity admits polylogarithmic update time with $Ω(n)$ words of space. In contrast, our lower bounds show that polynomial update time is necessary whenever $S\le n^{1-\varepsilon}$, even for a single pair of vertices and even for incremental algorithms with amortized guarantees.
Quantum protocols greatly reduce proof size for verifying network graphs
Quantum Advantage in Local Certification of Graph Properties
Abstract: Local certification allows network vertices to verify global properties using certificates from an untrusted prover and communication with their neighbors. Its complexity is the maximum certificate size at any vertex. Fraigniaud et al. (ITCS 2021) introduced the distributed quantum Merlin-Arthur (dQMA) model and proved an exponential quantum advantage for distributed equality, measured in input-string length. We resolve a question of Hasegawa, Kundu, and Nishimura (PODC 2024) by establishing unconditional exponential and polynomial quantum advantages for graph properties, which depend only on network topology, with complexity measured in the number $n$ of vertices. For every fixed integer $μ\ge 1$, we construct a graph property admitting a one-round dQMA protocol with $O(μ\log n)$-qubit certificates and messages, whereas every $μ$-round distributed Merlin-Arthur (dMA) protocol requires $Ω(n/(μ\log^2 n))$-bit certificates. We also give a one-round dQMA protocol for graph symmetry, the existence of a nontrivial automorphism, with $\widetilde{O}(n^{5/3})$-qubit certificates. This yields a polynomial advantage over one-round dMA protocols, for which an $Ω(n^2)$-bit certificate lower bound is known.
New bounds improve error rates for multiuser Gaussian communication channels
Non-asymptotic Sphere-Packing Bounds for Finite-Blocklength Scalar Gaussian Multiple-Access and Broadcast Channels
Abstract: This paper investigates non-asymptotic achievable rate regions of Gaussian multiple-access channels (MACs) and broadcast channels (BCs) in the finite-blocklength regime. By employing a proposed volume-uniform random coding (VURC) codebook that distributes codewords uniformly within an $n$-dimensional power sphere, together with successive interference cancellation (SIC) decoding, we derive a closed-form achievability bound, a scheme-specific lower bound on the average error probability, and a fourth-order asymptotic characterization. The proposed SIC achievability bound admits a simple and analytically interpretable closed-form expression, enabling direct performance evaluation without iterative computation. The structure of the proposed SIC asymptotic bound offers a highly extensible framework, allowing advances in single-user finite-blocklength theory to be systematically incorporated into the multiuser setting. Futhermore, to characterize the performance benefit of joint decoding, we further derive numerical and closed-form achievability bounds for the two-user Gaussian MAC under joint nearest-neighbor (JNN) decoding. Numerical results illustrate the performance differences among the proposed SIC and JNN bounds and existing benchmarks.
Hat guessing game limits match Lovász Local Lemma predictions
The Lovász Local Lemma Is Sharp for the Hat Guessing Number
Abstract: In the hat guessing game on a graph $G$, each vertex is occupied by a player wearing a hat whose color is chosen from a set of $q$ colors. Each player knows the graph and their position in it and sees only the hat colors of their neighbors. The players may agree on a strategy beforehand but must simultaneously try to guess their own hat colors without communicating. They win if at least one player guesses their own hat color correctly. The hat guessing number of $G$, denoted by $\textrm{HG}(G)$, is the largest integer $q$ for which the players have a strategy that guarantees a win for every assignment of hat colors. A direct application of the symmetric Lovász Local Lemma shows that $\textrm{HG}(G) < eΔ$ for every graph $G$ of maximum degree at most $Δ\ge 1$. We prove that this bound is asymptotically sharp: for every $\varepsilon > 0$ and every sufficiently large $Δ$, there exists a graph $G$ of maximum degree at most $Δ$ with $\textrm{HG}(G) \ge (e - \varepsilon)Δ$. This answers a question of Alon et al., disproves the conjecture $\textrm{HG}(G) \le 2Δ(G)$ of Bosek et al., and improves on the construction of Latyshev and Kokhas, which achieves $\textrm{HG}(G) = 4Δ(G)/3$. The hat guessing number thus provides a natural combinatorial problem in which the Lovász Local Lemma is asymptotically tight.
Distributed program creation depends on communication patterns
Distributed LTL Synthesis under Arbitrary Message Adversaries
Abstract: Reactive synthesis is the problem of generating a program that produces outputs satisfying a logical specification for every input stream. We study distributed synthesis for two processes communicating in rounds over unreliable links, with at least one message delivered in every round. Despite this delivery guarantee, we show that synthesis from linear temporal logic specifications is undecidable, even when messages carry the processes' complete causal histories. More generally, we give a complete characterization of the communication restrictions that make synthesis decidable. Restrictions are described by a message adversary $A$, a set of allowed infinite graph histories: sequences of communication graphs, each specifying which messages are delivered in a round. Iterated chromatic subdivision associates these histories with points in the unit interval, yielding an image $π(A) \subseteq [0,1]$. For every $ω$-regular message adversary $A$, synthesis is decidable if and only if $π(A)$ is nowhere dense. In the decidable cases, our procedure takes a deterministic parity automaton for $A$ and a specification, decides realizability, and constructs a realizing distributed algorithm whenever one exists. Further, our topological arguments shed new light on the fundamental requirements of synthesis. They show that, for $ω$-regular message adversaries, synthesis is decidable if and only if consensus is repeatedly solvable in bounded time. This links two previously unrelated problems from formal verification and distributed computing through the processes' uncertainty about communication.
Exact time to count agents in anonymous changing networks found
Computation in Anonymous Directed Dynamic Networks: Exact Worst-Case Termination Time and Network-Wise Intractability
Abstract: We determine the exact round complexity of Counting in anonymous directed dynamic networks. Agents have no identifiers, but $\ell\geq1$ of them are designated as leaders. Every agent knows $\ell$ and its own leader status, while the population size $n$ is unknown and has to be determined by the agents. Communication proceeds in synchronous rounds; the directed communication graph may change arbitrarily and unpredictably from one round to the next, but is assumed to remain strongly connected. We solve Counting with a distributed algorithm that makes every agent output $n$ and halt after a number of rounds equal to $\begin{cases} n&\text{if }n=\ell\\ 2n-1&\text{if }n>\ell\text{ and }\ell=1\\ 2n-2&\text{if }n>\ell\text{ and }\ell\geq2. \end{cases}$ The algorithm works even for networks with loops and parallel arcs and even when agents learn their outdegree only after sending. We prove that this bound is worst-case tight over directed multigraphs for every $n$ and $\ell$ with $1\leq\ell\leq n$. Moreover, the local computation is polynomial (provided that each communication multigraph has at most $2^{\operatorname{poly}(n)}$ arcs): in every round, each agent solves at most one linear system with up to $n$ variables. By standard techniques, solving Counting also enables the evaluation of any computable function of the multiset of agents' input values within $2n-1$ communication rounds. The bound above optimizes the worst case over all networks. For an individual network, we show that even deciding whether an agent already has enough local information to determine $n$ is $\mathsf{coNP}$-complete (provided that the numbers of parallel arcs are encoded in binary). Thus, worst-case-optimal Counting admits polynomial local computation, whereas exact network-wise optimization is intractable under standard complexity assumptions.
Anonymous parity certification requires logarithmic size certificates for sparse graphs
Tight Bounds for Anonymous Parity Certification
Abstract: Local certification is the task of verifying graph properties using certificates assigned to vertices and checked using only local information. A central question is which properties admit constant-size certificates, independently of network size. A fundamental test case is the parity of the network order. Bousquet, Feuilloley, Valenzuela, and Zeitoun (DISC 2026) showed that the complexity of certifying even order depends dramatically on the verification model. On arbitrary graphs, three bits per vertex suffice with unique identifiers and verification radius two. In the anonymous radius-one model, they established an $Ω(\log\log^* n)$ lower bound and an $O(\log n)$ upper bound. They also showed that constant-size certificates suffice in this model on bounded-expansion classes. In this paper, we settle the complexity of anonymous parity certification on general graphs and further investigate the role of graph sparsity. Our main contributions are: * We close the gap left by Bousquet et al., proving that the local complexity of certifying even order in the anonymous radius-one model is $Θ(\log\log n)$ bits. * We show that on graphs of degeneracy at most $d$, parity can be certified with $O(\log d)$ bits, while $Ω(\log\log d)$ bits are necessary. In particular, every class of bounded degeneracy admits constant-size certificates, strictly generalizing the result for bounded-expansion classes. * We show that constant-size certification cannot be guaranteed on nowhere-dense classes, a broader notion of sparsity that includes bounded expansion. We construct a fixed, subgraph-closed nowhere-dense class on which parity certification requires $Θ(\log\log n)$ bits. Together, our results provide a more complete picture of anonymous parity certification on sparse graph classes, showing that its complexity depends on the particular structural notion of sparsity.
Minimum samples needed to identify labeled coupon mappings
The Minimum Number of Samples in the Labeled Coupon Collector Problem
Abstract: The Labeled Coupon Collector Problem (LCCP) is an extension of the classical Coupon Collector Problem (CCP) in which one must deduce an unknown mapping between coupons and labels by collecting unordered subsets of k coupons and their associated labels, where deduction relies on analyzing the intersections and differences of the unordered subsets. In this work, we establish a fundamental connection between the LCCP and the combinatorial theory of separating systems. Using this framework, we completely characterize the minimum required number of samples to deduce all labels in two settings: Type-I, where the label set is known in advance, and Type-II, where it is unknown. We provide deterministic constructions of minimal separating and covering systems, yielding explicit bounds that are tighter than those found in existing literature. Furthermore, we extend our analysis to the partial recovery problem, characterizing the minimum number of samples required to identify a specified number of target coupons.
Largest codes with distances two or four solved for ternary and quaternary alphabets
The Ternary and Quaternary Cases of the $\{2,4\}$-Distance Code Conjecture
Abstract: For an integer $q\ge2$, let $A_q(n,\{2,4\})$ be the largest cardinality of an unrestricted $q$-ary code of length $n$ in which any two distinct words have Hamming distance $2$ or $4$. We prove that \[ A_q(n,\{2,4\})=1+\binom n2 \qquad(q\in\{3,4\},\ n\ge6), \] thereby settling the two remaining alphabet sizes in the conjecture of Boyvalenkov, Delchev, Zinoviev, and Zinoviev; the binary case was settled previously. The quaternary result implies the ternary result by alphabet inclusion. For $n\ge16$, the quaternary upper bound is proved combinatorially. After normalizing one word to zero, the weight-four supports form a $2$-intersecting family; exact support intersections force symbol synchronization and restrict support multiplicities. We combine the nontrivial intersection theorem with matching arguments and a three-coordinate projection lemma. The finite lengths $6\le n\le13$ are handled by a complete Hamming-isometry reduction to exact clique decisions, and $n=14,15$ by a smaller exact weighted-clique relaxation. All finite decisions are reproduced by two standalone integer-only C++17 verifiers provided as supplementary source files.
Interactive communication limits for secure multi party sum calculation
The Capacity of Interactive Secure Summation
Abstract: In secure summation, $K$ parties each hold an input, and the sum of the inputs is computed at one party, securely against at most $T$ colluding parties. Communication typically takes one hop: each party sends one message directly to the party that computes the sum, using correlated randomness that is independent of the inputs and held in advance. We consider interactive secure summation, where every pair of parties is connected by a secure link, so that each party can send messages to every other party, each party has only independent local randomness, and the messages may depend on the inputs and on earlier messages over multiple rounds. We characterize the capacity region, the set of achievable rates of communication, counting all messages exchanged among the parties over all rounds, and of the randomness of every party, counted in symbols per symbol of the sum. For $0\le T\le K-2$, the optimal communication rate is $K(K-1)/(K-T)$, and the randomness rates form a polyhedron with, up to a relabeling of the parties, a single extreme point: $T$ parties have the randomness rates $(K+T-2t)/(K-T)$, $t=1,\ldots,T$, and the others none. In particular, the optimal total randomness rate is $T(K-1)/(K-T)$. Linear schemes achieve every extreme point together with the optimal communication rate. The same techniques give the capacity region when every party recovers the sum and when the sum is computed at a server without input.
New choreographic logic links program proofs and network behaviors
Two Sides of the Same Proof: Extraction and Projection in Choreographic Programming
Abstract: A new approach to the theory of choreographic languages has recently been proposed, based on the interpretation of choreographies with finite behaviors as proofs in an extension of linear logic. This paper further develops this approach to cyclic proofs to be capable of representing infinite behaviors, and prove a completeness result for choreographies with respect to the class of lock-free networks. We show that in a choreographies-as-proofs correspondence, the proof equivalence induced by rule permutations corresponds to bisimilarity, and that, under adequate assumption on the procedure definitions, the proof search procedure has a finite search space, and can be used to extract a choreography from a network.
Optimal limits found for repairing data with fixed code splitting
From Linear Exact Repair to Mixed-Alphabet Codes: The Bandwidth-Subpacketization Tradeoff of MDS Array Codes
Abstract: MDS array codes achieve optimal storage efficiency in distributed storage systems, but their repair bandwidth depends critically on the sub-packetization level. While the theoretically optimal repair bandwidth (i.e., cut-set bound) of a high-rate exact-repair MDS array code is attainable with sufficiently large sub-packetization, the fundamental limits for fixed sub-packetization remain poorly understood. We study this problem for centralized linear exact repair of $h$ failures from $d$ helper nodes over a fixed finite field. We show that the rank profile of any linear repair scheme is constrained by two auxiliary mixed-alphabet codes. The first code is formed from the kernels of the helper projections and exists for all repair degrees; the second is formed from their row spaces and applies in the full-helper regime when $d\ge r$. These codes have complementary alphabet profiles, and their size and minimum-distance requirements are forced solely by the MDS property and repair correctness. This gives a unified route from classical coding-theoretic upper bounds to repair-bandwidth lower bounds. As a consequence, we obtain several explicit lower bounds via Singleton, Hamming, Plotkin, and Griesmer arguments, including known bounds as corollaries. We further formulate a Delsarte-type support-enumerator LP for mixed-alphabet codes and give an exact type-compressed implementation. For fixed sub-packetization \(\ell\), this yields a polynomial-time procedure for evaluating the resulting finite-parameter lower bound.
Exact tradeoffs found for repairing failed storage systems
Exact Storage-Repair-Bandwidth Tradeoffs for $(6,5,5)$ and $(7,6,6)$ Exact-Repair Regenerating Codes
Abstract: This note provides exact information-theoretic outer bounds that completely characterize the storage-repair-bandwidth tradeoff regions for the cases $(n,k,d)=(6,5,5)$ and $(7,6,6)$. The layered code proposed by Tian et al. achieves the tradeoff and is thus optimal. GPT-6 Astra assisted in the discovery of these bounds, based on a new conditioning argument and a structured search over the restricted subsets of entropy linear program constraints. The proofs are given as exact integer-valued certificates, which are difficult for direct human verification, and a Python verifier is included as part of the package, together with the certificates.
Alternating local certifications reveal power limits in anonymous networks
On the Power of Alternating Local Certification with Constant-Size Certificates
Abstract: We study alternation hierarchies for distributed decision in anonymous networks with constant-size certificates. A prover and a disprover alternately assign certificates to nodes over a constant number of rounds, after which each node decides whether to accept based on its own input and the certificates observed in its neighborhood. An instance is accepted if all nodes accept. Unlike previous work on distributed alternation hierarchies, which considered restricted local computation (Reiter, PODC 2024) or logarithmic-size certificates (Feuilloley et al., ICALP 2016), we focus on constant-size certificates and the role of neighborhood information in determining expressive power. We consider three models: SET, where nodes observe only the set of certificate sequences of their neighbors; MULTISET, where multiplicities are also visible; and PORTS, where neighbors can additionally be distinguished by local port numbers. We establish that SET is strictly weaker than MULTISET, which is in turn strictly weaker than PORTS, and that all three alternation hierarchies are strict at every level. Despite their severe restrictions, these models are remarkably expressive: LEADER belongs to the third level of SET. Our main characterization shows that, over finite input alphabets, SET coincides exactly with monadic second-order logic (MSO$_1$). Moreover, every language definable in counting monadic second-order logic (CMSO$_1$) belongs to PORTS, while MULTISET already contains languages that are not CMSO$_1$-definable. Nevertheless, this expressive power has fundamental limitations. PORTS does not capture MSO$_2$: neither Hamiltonicity nor the existence of a perfect matching belongs to PORTS. Furthermore, over unbounded input alphabets, PORTS cannot verify that every node has been given the correct network size.
Video streaming stays smooth despite huge packet losses
Tokenized Joint Source-Network Coding for Loss-Resilient Video Streaming
Abstract: For decades, conventional video streaming systems have relied on packet-level forward error correction (FEC) codes and retransmissions to ensure reliable video delivery. However, in real-time communications, FEC is inherently inefficient under unknown and time-varying packet-loss conditions, while retransmission can incur excessive latency and fail to meet stringent playout deadlines. Emerging deep joint source-channel coding (DeepJSCC) provides an alternative by learning channel-noise-resilient representations, yet its tight coupling with the physical layer makes it difficult to integrate into today's layered network architectures and protocols. In this paper, we propose TokJSNC, a simple-but-effective tokenized joint source-network coding paradigm for packet-loss-resilient video streaming. Rather than first compressing video into a compact bitstream and then protecting it with packet-level FEC, TokJSNC directly encodes video into variable-length discrete token-stream, whose transmission rate is jointly adapted to video content complexity and network conditions. By exploiting the spatiotemporal correlations among learned video tokens, TokJSNC enables robust video reconstruction over a wide range of packet-loss rates without explicit FEC or retransmissions. Consequently, TokJSNC brings the JSCC-like graceful degradation property to the network layer while remaining compatible with existing network architectures and transport protocols. Experimental results show that TokJSNC maintains an average playback frame rate above 22 fps even at a 70% packet-loss rate, whereas the best-performing baseline drops below 12 fps. Overall, TokJSNC establishes a practical pathway for repurposing modern generative video tokenizers for loss-resilient streaming, while providing a fundamental framework for video token communications.
Cache helps reduce communication for distributed linear computations
Cache-Aided Linear Function Computation
Abstract: We study cache-aided linear computation in distributed systems where each source generates and stores its own data. An external receiver requests a linear combination of these data, and the sources use information cached before the request is known to reduce the communication needed to recover the requested result. In our model, each of the $N$ sources stores its own independent file over a finite field and has an additional cache of normalized size $M$. The receiver must recover any requested linear combination with zero error from the messages sent by the sources over separate noiseless links. We establish a lower bound on the worst-case communication rate over any finite field by analyzing several requests under the same cache placement. This bound determines the optimal rate when no additional cache is available. For binary files, we propose parity-aided placement (PAP), a coded-placement scheme that combines cached parities with uncoded symbols. For every $N\geq3$, we characterize its communication rate for each request and optimize its placement parameters to obtain a closed-form worst-case rate. The resulting achievable rate meets the lower bound for $0\leq M\leq1/(2N-1)$ and $M\geq(N-1)/N$, establishing the optimal memory--rate tradeoff in these two ranges.
Channel communication method enables joint message sending and state sensing
Joint Identification, Transmission, and Sensing over State-Dependent Channels with Noiseless Feedback
Abstract: We consider a discrete memoryless state-dependent channel with noiseless feedback, where the transmitter uses randomized encoding to jointly perform message transmission, identification, and state sensing. In this setting, the transmitter sends a conventional transmission message and an identification message while estimating the unknown channel state sequence under an average distortion constraint. We establish a single-letter characterization of the randomized identification-transmission-sensing capacity-distortion region. The result reveals a single-letter separation structure: the communication rates are determined by the averaged channel, subject to the sensing-induced constraint on admissible input distributions. Specifically, the transmission rate is characterized by mutual information, while the identification rate is characterized by output entropy under the same distortion constraint. The achievability proof combines constant-composition transmission coding, output partitioning, and combinatorial identification coding, while the converse follows from an averaged-channel reduction, distortion lower bounds, and feedback-identification converse arguments.
Non-adaptive set membership schemes improved by removing extra logarithmic factor
Revisiting Non-Adaptive Set Membership Schemes: Removing the Logarithmic Factor
Abstract: We study non-adaptive bit-probe schemes for static set membership. Each query reads a fixed number of bits and answers by strict majority. We revisit the random bipartite-graph construction of Garg and Radhakrishnan [STACS, 2017]. The main observation is that a slightly stronger expansion property already bounds the number of exceptional elements. This makes a separate probabilistic estimate for exceptional elements unnecessary. A detailed union-bound calculation then gives, for every fixed $t\ge5$, a logarithm-free existence bound of $O_t(m^{1/c}n^{1-1/c})$, where $c=\lfloor(t-1)/2\rfloor$. For odd $t$, this removes the logarithmic factor from the general upper bound of Garg and Radhakrishnan [STACS, 2017].
No faster distributed algorithms exist for maximal independent sets
No Truly Sublogarithmic-Round Algorithm for Distributed MIS in the LOCAL Model
Abstract: We prove that $o(\frac{\log n}{\log\log n})$-round randomized LOCAL algorithms find a maximal independent set (MIS) with subconstant probability on some input. This shows that the 40-year-old $O(\log n)$-round randomized CONGEST algorithm of Luby and Alon, Babai, and Itai is nearly optimal. Our lower bound improves upon the $Ω(\sqrt{\log n})$-round lower bound of Khoury and Schild and nearly closes the 20+ year-old gap between the $O(\log n)$-round algorithm and the $Ω(\sqrt{\frac{\log n}{\log\log n}})$-round lower bound of Kuhn, Moscibroda, and Wattenhofer. To close this gap, one must show a lower bound for a graph that is not locally treelike. We do this by starting with a $D$-regular, $Θ(\log_D n)$-girth graph, with $D = Θ(\log n)$. Crucially, this is not our final graph. We obtain our hard instance by \emph{replacing} each vertex of this treelike graph with a clique on $n^c$ vertices for some constant $c \in (0,1)$. We then replace each edge with a bipartite Erdős--Rényi graph between the corresponding cliques, with each edge present independently with probability $1/2$. We analyze arbitrary LOCAL algorithms on our non-treelike hard instance with a novel round elimination approach. We describe algorithms that output a set of vertices in this graph using two metrics: their \emph{occupancy probability} and their \emph{conflict probability}. Our round elimination framework takes an $r$-round algorithm and produces an $(r-1)$-round algorithm where occupancy and conflict probabilities collectively slightly degrade, but individually can significantly improve or degrade. This round elimination result is obtained by exploiting the lack of large biclique complements in dense bipartite Erdős--Rényi graphs, which in turn allows us to bound the entropy of the output distribution for any independent set algorithm.
Discrete Wyner Ziv problem second order coding rates improved
Exact Second-Order Asymptotics for the Discrete Wyner--Ziv Problem
Abstract: We revisit the discrete Wyner--Ziv problem and establish exact second-order asymptotics. Our main contribution is a second-order converse bound, which is derived using posterior decomposition, concentration inequalities, and a conditional Gaussian approximation for martingales. Furthermore, we extend the previous best known achievability result of Li and Li (arXiv 2025) by allowing the test channel to depend on the type of the observed source sequence. Exact second-order asymptotics are established by combining our achievability and converse bounds. In particular, we show that the achievability bound of Li and Li (arXiv 2025) is not optimal in general. Specifically, we provide two numerical examples to illustrate our results: a binary asymmetric source and a quaternary source. For the first example, the achievability bound of Li and Li (arXiv 2025) achieves the optimal second-order asymptotics. However, in the second example, we show that our achievability result is optimal, which reduces the second-order coding rate of Li and Li (arXiv 2025) by $10.77\%$ at the excess-distortion probability of $0.1$ and by $21.35\%$ at the excess-distortion probability of $0.2$.
Symbolic algorithms identify winning strategies in multiplayer games
Antichains for Concurrent Parameterized Games
Abstract: Concurrent parameterized games involve a fixed yet arbitrary number of players. They are described by finite arenas in which the edges are labeled with languages that describe the possible move combinations leading from one vertex to another (n players yield a word of length n). Previous work showed that, when edge labels are regular languages, one can decide whether a distinguished player, called Eve, has a strategy to ensure a reachability objective, against any strategy profile of her arbitrarily many opponents. This decision problem is known to be PSPACE-complete. A basic ingredient in the PSPACE-membership proof is the reduction to the exponential-size knowledge game, a 2-player game that reflects the knowledge Eve has on the number of opponents. In this paper, we provide a symbolic approach, based on antichains, to compute Eve's winning region in the knowledge game. In words, it gives the minimal knowledge Eve needs at every vertex to win the concurrent parameterized reachability game. More precisely, we propose two fixed-point algorithms that compute, as an antichain, the maximal elements of the winning region for Eve in the knowledge game. We implemented these two algorithms in C++, as well as the one initially proposed, and report on their relative performances on various benchmarks.
Dynamic graph problem update and query times must grow squared log ratio
$Ω((\log n/\log\log n)^2)$ Lower Bounds for Dynamic Graph Problems
Abstract: We prove an $Ω((\log n/\log\log n)^2)$ unconditional lower bound on the maximum of the query time and update time for dynamic data structures supporting reachability queries in $n$-node directed acyclic graphs under edge insertions. This improves the $\widetildeΩ(\log^{3/2} n)$ lower bound of Larsen and Yu [SICOMP 2025], and matches the strongest lower bound known for any dynamic problem. The same bound holds for incremental undirected shortest paths and subgraph connectivity. To prove it, we bring the recent framework of Ko [FOCS 2026], which gave this bound for Pătraşcu's multiphase problem with Inner Product, to the multiphase problem with Disjointness. Our main technical contribution is to show that verification in Ko's 2.5-round multiphase communication game makes a one-sided corruption bound suffice in place of discrepancy, which Disjointness lacks.
Thermodynamic digital twins cut communication in swarm control
Thermodynamic Digital Twins: Physics-Native Semantic Synchronization for 6G Kinetic Swarms
Abstract: The synchronization of large-scale kinetic swarms with digital twin networks can generate substantial signaling overhead when predictable motion is repeatedly reported. To reduce such redundancy, we propose the thermodynamic digital twin (TDT), a physics-guided synchronization framework that combines field-based state extrapolation with event-triggered correction. For a closed domain with vanishing boundary flux, the divergence--entropy relation is used as a physical motivation for identifying structural changes in the reconstructed swarm field. Based on Reynolds decomposition, the hierarchical thermodynamic synchronization (HTS) protocol separates low-dimensional macroscopic drift updates from full-state microscopic corrections. A locally measurable smoothed-particle-hydrodynamics descriptor, combining velocity divergence and acceleration, provides an implementation-oriented early-warning trigger, while a transport-error analysis provides a short-interval rule for limiting silent extrapolation. The same extrapolation mechanism is further used as a predictor-like delay compensator in the closed-loop digital twin. Across the evaluated numerical settings, TDT reduces the generated edge-to-cloud synchronization payload relative to the considered baselines and exhibits a favorable empirical trade-off between tracking error and communication cost. The results also indicate improved delay tolerance in the evaluated control loop.
Universality reduces reliability in classical quantum communication channels
Universality Sacrifices Reliability in Classical-Quantum Channel Coding
Abstract: Universal channel coding enables communication without a complete description of the channel. For classical channels, universal codes can attain both capacity and the optimal high-rate reliability. We show that this compatibility fails for classical-quantum channels in general; that is, the optimal reliability in the channel-aware scenario is not always achievable with universal coding due to the ignorance of the unitary rotation of the output system. We exhibit a family of classical-quantum channels for which one cannot achieve the channel-aware optimal reliability by a fixed coding scheme. We further derive a converse bound on the reliability for unitary-invariant decoders, a natural assumption for the universal coding scheme, that can be strictly smaller than the optimal channel-aware error exponent. Conversely, we construct a channel-independent encoder-decoder pair and establish a universally achievable bound on the reliability that matches this converse bound in the high-rate regime, thereby characterizing the optimal universal reliability. Specifically, the channel-aware and universal exponents are governed by the Petz and sandwiched Rényi divergences, respectively. These divergences coincide for commuting outputs but differ for noncommuting ones, explaining why universality preserves optimal reliability classically but can reduce it quantumly. Our results showcase the fundamental reliability cost of performing the classical-quantum channel coding task universally.
Rank-preserving locality theorem simplifies logic analysis on weighted structures
A Rank-Preserving Gaifman Normal Form for First-Order Logic on Weighted Structures
Abstract: We prove a rank-preserving version of Gaifman's Theorem. Compared to earlier rank-preserving locality theorems (in particular, [Grohe, Kreutzer, Siebertz, JACM 2017]), our theorem is much simpler and yields formulas in exactly the same normal form as Gaifman's original theorem. Furthermore, it holds not only for first-order logic, but also for first-order logic with modulo-counting quantifiers and, more generally, for the first-order logic on weighted structures ngFOW+ that is introduced in this article. As an application of our theorem, we give a simplified proof of the algorithmic meta-theorem of [Grohe, Kreutzer, Siebertz, JACM 2017] stating that first-order properties of nowhere dense structures can be decided in almost-linear time. Our locality theorem for the weight logic ngFOW+ can be seen as an essential step toward such a meta-theorem for this logic.
Asynchronous message passing gains reversible computation properties
On Asynchrony and Reversibility in CCS
Abstract: Asynchronous communication is a fundamental feature of modern distributed systems, where messages are emitted without requiring immediate synchronization with receivers. In process calculi, this behaviour is typically modelled by separating message emission from message consumption. At the same time, reversible computation has emerged as an important paradigm for analysing concurrent systems, enabling computations to be undone while preserving causal dependencies between actions. While reversible semantics have been extensively studied for synchronous process calculi such as CCS, their integration with asynchronous communication remains largely unexplored. In this paper we investigate the interaction between asynchrony and reversibility in the setting of CCS. We first introduce CCSa, an asynchronous variant of CCS in which output actions generate explicit message entities that can later be consumed by matching input actions. We then define rCCSa, a reversible extension of CCSa obtained by adapting the framework of Phillips and Ulidowski. In rCCSa, prefixes and messages are annotated with unique keys that record message emission and consumption events, allowing computations to be reversed while preserving causal dependencies. We show that the resulting reversible semantics satisfies causal consistency, ensuring that computations can be reversed exactly up to causal equivalence. The proof relies on the axiomatic framework for reversible computation proposed by Lanese et al.
Distributed graph problems need longer randomized algorithms
Distributed Lower Bounds via Automatic Self-Reduction
Abstract: The development of round elimination into a general-purpose technique [PODC 2019] marked a turning point in our understanding of the hardness of many graph problems in the distributed setting and led to several breakthrough results. However, the round elimination technique seems unable to yield randomized lower bounds of $ω(\log \log n)$ rounds as a function of the number $n$ of nodes. Very recently, Khoury and Schild [FOCS 2025] introduced a new technique called round elimination via self-reduction, which bypasses the limitations of classical round elimination. Using this approach, the authors show that any randomized algorithm for maximal matching requires $Ω(\sqrt{\log n})$ rounds in the LOCAL model. Their elegant technique is, in some respects, similar to classical round elimination while being fundamentally different in others. However, it is tailored specifically to maximal matching rather than being applicable to a broad class of problems. In this paper, we show that self-reduction is, in fact, a special case of classical round elimination, thereby turning it into a general-purpose approach. In particular, we introduce a new way to measure the error of an algorithm and show that, under this new measure, classical round elimination can indeed yield $ω(\log \log n)$ randomized lower bounds. More specifically, we identify a large class of problems for which this improvement is entirely black-box: once a problem is shown to belong to the class, stronger randomized lower bounds follow automatically from the classical round-elimination framework. As an application, we prove $Ω(\sqrt{\log n})$ randomized lower bounds for a range of graph problems, namely, maximal matching on regular $2$-colored graphs, $\frac{1}{k}$-integral matching, and maximal $H$-packing.
Bounded decoders improve error and erasure estimates in short block communication
Block Erasure Channel and Block z-Channel with Bounded Decoders and Finite Blocklength
Abstract: Block error rate is a standard metric in finite blocklength (FBL) communication, yet it conflates two qualitatively different failure modes: block confusions, where the decoder selects a wrong codeword, and block erasures, where it declares a loss. Higher-layer protocols treat physical-layer failures as erasures, but this cross-layer assumption lacks FBL justification. We derive a rigorous upper bound and a companion lower-side estimate on the block confusion probability (BLCP) and block erasure probability (BLEP) for bounded-distance decoders over additive white Gaussian noise (AWGN) channels at finite blocklength, recasting the coding problem as a geometric sphere packing one. We analyze the sensitivity of these bounds to blocklength and signalto-noise ratio, characterize the envelope of the upper bound, and derive closed-form Chernoff approximations. Extending the model to idle transmission blocks, we bound the false alarm probability (FAP) and show that a block z-channel abstraction emerges from the bounded-decoding geometry. Numerical results confirm that confusion and false alarm probabilities lie far below the error rate constraint, providing quantitative physicallayer support for the block erasure channel and block z-channel abstractions assumed in protocol design.
Binary deletion channel capacity approximated within one hundredth bit
Binary Deletion Channel Capacity to Within One Hundredth of a Bit
Abstract: The exact capacity of the binary deletion channel remains unknown despite decades of work on achievable rates and converse bounds. We establish a computer-assisted approximation whose error is below $0.0095$ bits per transmitted bit, uniformly over all deletion probabilities. The mean certified error bound, with uniform weighting of deletion probability, is below $0.006522$. The estimate is the midpoint of explicit lower and upper bounds. For the converse, a stationary-source reduction is combined with finite inequalities covering every allowed input configuration. Two constructions control the unobserved input beyond a finite window: one uses a common outside survivor sequence and bounds omitted deletion patterns, while the other cancels an entropy term to make outside probabilities enter linearly. For the lower bound, finite-state inputs combine output-entropy estimates with selected disjoint counts of compatible deletion masks; independent-run inputs retain additional uncertainty about output-run boundaries. Directed numerical checks establish the finite inequalities. An analytic comparison between deletion probabilities then extends the pointwise bounds over the entire parameter range. The lower endpoint supplies rates within $0.019$ bits of capacity in the asymptotic coding sense. We give the derivations, recorded computational costs, and complete numerical inputs and programs needed to verify the result.
New framework links memory and query costs in matrix data structures
Systematic Data Structure Lower Bounds via the Query-with-Sketch Model
Abstract: We study data structure lower bounds for the Approximate Matrix Powering (AMP) problem. Given a substochastic, symmetric matrix $\mathbf{M}\in\mathbb{R}^{n\times n}$ and parameters $k$ and $α$, the goal is to preprocess $\mathbf{M}$ so as to answer entry queries $(u,v)\mapsto \mathbf{M}^{k}[u,v]$ up to additive error $1/n^α$. We focus on AMP in the succinct and systematic regime, in which the data structure stores $\mathbf{M}$ verbatim, uses an additional $r$ bits of redundancy, and must answer queries by probing only a small number of entries of $\mathbf{M}$. Our main conceptual contribution is a general framework for proving probe--redundancy trade-offs for systematic data structures. We introduce the query-with-sketch model and develop a min-entropy-based approach that lifts conditional min-entropy bounds in the absence of redundancy to probe lower bounds in the presence of redundancy. We then establish these min-entropy bounds using problem-specific analytic and algebraic tools, for the downstream applications to AMP and its variants. As a consequence, our results provide new unconditional evidence toward a conjecture of Patrascu and Roditty (2010) on the space required for constant-time set-disjointness queries.
Price of anarchy grows with network size in max-distance games
The price of anarchy in the max-distance network creation game is not constant
Abstract: At edge price $α=1$, we construct an infinite family of pure Nash equilibria of the unilateral max-distance network creation game with $\PoA\ge2^{\sqrt{\log_2 n}-O(\log\log n)}$. Together with the known upper bound, this gives $2^{Θ(\sqrt{\log n})}$ along the constructed sequence of population sizes. We subdivide every edge of the bipartite double cover of a distance-uniform graph with large diameter constructed by Lavrov, Loh and Messegué, and let each subdivision vertex buy its two incident edges. A distance calculation rules out every profitable unilateral deviation. The equilibria are not strict. We also give a short proof that the price of anarchy is constant for every polynomially vanishing edge price.
Semantic aware error recovery improves AI data movement latency
SAGE: Semantic-Aware Geographic Error Recovery for AI Data Movement
Abstract: AI interconnects typically protect and replay packets uniformly, yet numerical bit faults differ sharply in consequence: a low-order mantissa flip may resemble quantization noise, while a high-significance exponent flip can produce a catastrophic outlier or non-finite value. We present SAGE, a semantic-aware geographic error-recovery architecture that decouples whether a detected fault merits replay from where replay restarts. For BF16-like data, a workload-calibrated contract separates catastrophic Class-H faults from bounded Class-M and precision Class-L damage. It first applies a Class-H silent-delivery constraint, then ranks admissible policies by quality-normalized terminal latency, $Ψ_{\rm del}$. Independently, a source-local region table adapts checkpoint intervals to fault geography, shortening recovery segments in noisy regions. Detected Class-H failures may trigger protected negative acknowledgments and full-flit replay; Class-M and Class-L outcomes do not trigger default network replay. We implement SAGE's endpoint and replay protocol in gem5 Garnet and synthesize its fully pipelined checker in ASAP7. At a stable synthetic operating point, a ten-seed contention-faithful direct-Garnet campaign shows that SAGE reduces $Ψ_{\rm del}$ by 30.1% relative to fixed 34-hop recovery, combining 28.0% lower mean latency with improved delivered semantic quality. Under higher-BER synthetic stress at the same offered load, SAGE maintains bounded queues while the fixed baseline accumulates backlog. Application-derived DeiT-S communication traces also show lower mean and p99.5 latency at the evaluated nonzero BERs. Within the qualified operating envelope, CRC32 decoder trials yield a simultaneous 95% per-original Class-H silent-delivery upper bound of $3.18\times10^{-7}$.