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.

Fri 13 NovInformation Theory
The gist
This paper explores a special way to measure distances in codes, called the lambda-subfield metric, which helps understand error-correcting codes better. The authors study the best possible codes under this metric, discovering new rules about their structure and frequency in large systems. They also find new mathematical limits that codes must follow and identify specific code families that meet these limits. Finally, they add new versions of classic bounds used in coding theory to this setting. These results help deepen understanding of code design using this newer metric.
Open → 2611.18228v1

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)..

Fri 13 NovDistributed, Parallel, and Cluster Computing
The gist
When networks fix themselves after errors by recoloring nodes, it usually takes some time to settle. The authors study how long this fixing process takes on average, how much that time varies, and the full probability of all outcomes on different kinds of network shapes. They focus on a classic method where nodes change their colors one by one at random, and they find formulas that depend on the local network structure. This gives a clearer picture than just worst-case time estimates.
Open → 2611.17989v1

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.

Sun 8 NovCryptography and SecurityNetworking and Internet Architecture
The gist
Modern self-driving cars communicate with other cars and road systems to make driving decisions. If someone sends fake messages, it can cause dangerous driving choices. The authors created a system that simulates these attacks and tracks how cars respond over time, helping to see the chain reaction of events on the road. This system is flexible and lets users add new types of attacks and monitor how vehicles and traffic behave under these conditions.
Open → 2611.11627v1

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.

Fri 6 NovComputational Complexity
The gist
Finding if one point can reach another along a path is a common problem in networks. The authors found new ways to decide reachability in certain directed graphs drawn on surfaces with restricted cycle or cut patterns. Their methods use special weighting tricks that make the problem easier to solve using less memory. These results provide better understanding of how hard reachability is in these structured graphs and improve related problems like perfect matching in bipartite graphs.
Open → 2611.09262v1

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.

Thu 5 NovData Structures and Algorithms
The gist
Finding out if two points are connected in a changing network usually gets faster if the computer uses more memory. This paper studies how well algorithms can do when they have only a small, fixed workspace and read-only access to the network, which keeps changing by adding or removing links. The authors find lower bounds on how much time it takes to update connectivity info depending on memory size and how the network is accessed, showing that if memory is limited, the updates must take much longer. Their results show a tradeoff: less memory means slower dynamic graph algorithms even for simple cases.
Open → 2611.08351v1

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.

Thu 5 NovDistributed, Parallel, and Cluster Computing
The gist
Verifying big network structures usually requires sharing large pieces of information locally. This paper shows that using quantum communication can drastically shrink the amount of information needed to prove certain network properties. The authors demonstrate this by constructing specific graph properties where quantum methods require exponentially or polynomially smaller proofs compared to traditional ones. This means networks could verify global properties more efficiently with quantum tools.
Open → 2611.08076v1

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.

Tue 3 NovInformation Theory
The gist
Communication over wireless networks involves sending messages from multiple users to a receiver or from one sender to many receivers. The authors studied how well these messages can be sent when the message length is short, which is important for fast and reliable communication. They introduced a new method for constructing messages and decoding them that allows exact calculation of error probabilities without complex computations. Their work also compares different decoding approaches and shows how improvements for single users can help in multiuser scenarios.
Open → 2611.04647v1

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.

Tue 3 NovDiscrete Mathematics
The gist
The paper studies a hat guessing game played on a network where each player can only see their neighbors' hat colors. The main question is how many colors can be used while still guaranteeing that someone guesses correctly every time. The authors prove that a known mathematical bound called the Lovász Local Lemma is nearly exact in this setting. This resolves a previous open question and disproves a prior guess about the game's limits. Their result shows the hat guessing number can be as large as nearly e times the maximum number of neighbors.
Open → 2611.04577v1

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.

Tue 3 NovDistributed, Parallel, and Cluster ComputingFormal Languages and Automata TheoryLogic in Computer Science
The gist
Creating programs that react correctly in a distributed system is tricky when messages between parts may be lost. This paper finds that deciding whether such a program can exist is impossible in many scenarios, even when some messages always get through. The researchers describe exactly which communication patterns allow deciding this and provide a method to build correct programs when it is possible. They also reveal a surprising connection between being able to reach agreement quickly and being able to synthesize these programs.
Open → 2611.04561v1

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.

Sun 1 NovDistributed, Parallel, and Cluster Computing
The gist
Counting how many agents are in a network where agents have no names and the connections change unpredictably is a tricky problem. The authors figure out the exact number of steps needed for all agents to know the total count and stop, depending on leaders present. They also show that their method runs efficiently, but deciding exactly if one agent has enough information early is very hard computationally. This means their solution is the best worst-case strategy, though optimizing for a specific network is much more difficult.
Open → 2611.01761v1

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.

Wed 28 OctDistributed, Parallel, and Cluster Computing
The gist
Checking if a network graph has an even or odd number of nodes can be tricky when nodes have no unique IDs and can only see their immediate neighbors. The authors show the smallest amount of information (certificate size) each node needs to verify the network’s parity depends on how sparse or connected the graph is. They find exact bounds for general graphs and explore how different notions of sparsity affect this verification complexity. This helps understand the limits of local checking in networks without unique identifiers.
Open → 2610.38829v1

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.

Fri 23 OctDiscrete Mathematics
The gist
The coupon collector problem is about collecting all types of coupons, but this paper studies a tougher version where the connection between coupons and labels is unknown and must be figured out from samples. The authors find the least number of samples required to completely identify which coupon has which label in two different cases: when the label set is known and when it isn’t. They also show how to build the minimal sample collections needed. Additionally, the paper looks at partial identification, determining the minimum samples needed to identify some of the coupons.
Open → 2610.32251v1

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.

Thu 22 OctInformation Theory
The gist
This paper settles a long-standing puzzle about how big certain sets of codes can be when any two code words differ in exactly two or four positions. The authors prove the biggest possible size for these codes when the code symbols come from three or four options, completing the picture started by earlier work on two-symbol codes. They use a mix of combinatorial reasoning and computer-assisted verification to cover all cases. Their work narrows down the structure and size of these special code sets for longer word lengths.
Open → 2610.30615v1

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.

Wed 21 OctInformation Theory
The gist
Sometimes many people want to securely add their secret numbers together without anyone else finding out their individual numbers. Usually, everyone just sends one message directly to a special person who adds them up. This paper studies what happens when everyone can talk many times to each other using secret messages and only their own random choices. The authors figured out the best possible communication and randomness needed so that the sum can be computed securely, even if some people try to cheat or collaborate secretly. Their results show exactly how much talking and random secret information each person must use in this interactive setting.
Open → 2610.29954v1

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.

Wed 21 OctLogic in Computer Science
The gist
Communicating computers often follow preset sequences called choreographies to avoid confusion or deadlock. This paper shows how such choreographies can be analyzed and created using ideas from logic, treating them like mathematical proofs. The authors extend previous work to handle repeated or endless behaviors and prove their method fully captures a wide range of safe network interactions. They also show how to recover a choreography by examining the network communication patterns themselves.
Open → 2610.29736v1

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.

Wed 21 OctInformation Theory
The gist
Distributed storage systems save data efficiently using special error-correcting codes, but fixing broken parts requires bandwidth that depends on how the data is split. The authors study how much bandwidth is needed when data splits are fixed and code repair is done linearly. They link repair limits to two types of mixed-alphabet codes, which are constrained by the system's properties. This connection lets them use known coding theory bounds to prove new lower bounds on repair bandwidth, and gives a way to compute these limits efficiently for any fixed data split.
Open → 2610.29144v1

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.

Tue 20 OctInformation Theory
The gist
Storing data safely across many computers means you need to fix lost pieces quickly and without using too much space or communication. This paper finds the exact best balance between how much data each computer stores and how much information needs to be shared to repair a failure in certain setups with six or seven storage nodes. The authors also confirm that an existing layered coding method perfectly matches this balance. They used advanced mathematical tools, assisted by AI, to prove these limits exactly.
Open → 2610.28199v1

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.

Fri 16 OctDistributed, Parallel, and Cluster Computing
The gist
This paper explores how small pieces of information shared by nodes in anonymous networks help them decide if the whole network meets certain conditions. The authors show that giving nodes different ways to see their neighbors' information changes what the network can decide. They find that some network properties can be decided with very limited information, while others cannot. Their work helps clarify what types of network problems are solvable with simple certificates and local views.
Open → 2610.23694v1

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.

Thu 15 OctMultimedia
The gist
Video streaming often struggles when many packets of data get lost, causing delays or poor quality. The authors propose TokJSNC, a new way to send video that breaks it into special tokens instead of traditional data packets. This method adjusts to network conditions and video complexity to keep videos playing smoothly, even when lots of data is lost, without needing extra fixes like retransmissions. Experiments show it can keep frame rates high where other methods fail.
Open → 2610.21166v1

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.

Wed 14 OctInformation Theory
The gist
When many separate sources each hold different pieces of data, sometimes we want to combine their data in a specific way by adding and multiplying them. This study looks at how storing extra helpful bits in advance, before we know exactly what combination is needed, can save time communicating later. The authors found limits on how much communication can be saved and introduced a smart way to store extra data bits, which is best in some cases. Their method works well especially when the storage is very small or nearly full.
Open → 2610.20323v1

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.

Wed 14 OctInformation Theory
The gist
This paper studies how a transmitter can send messages and identify information while also guessing unknown channel conditions, all at once. The authors show how to find the best balance between sending information and sensing the channel without extra noise. They provide formulas that describe how much information can be sent and identified while keeping sensing accurate. Their approach cleverly combines several coding techniques and proves these rates are optimal given the constraints.
Open → 2610.19784v1

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].

Wed 14 OctData Structures and Algorithms
The gist
Checking if an item belongs in a set can be done efficiently by reading only a few bits from a data structure. The authors revisited a previous method that used random graphs and discovered a way to simplify the math by ensuring a stronger connection property. This led to a clearer calculation that removes an extra multiplying factor in the scheme’s size for cases reading five or more bits. This means certain data structures for set membership can be made slightly smaller without sacrificing reliability.
Open → 2610.19706v1

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.

Tue 13 OctData Structures and AlgorithmsDistributed, Parallel, and Cluster Computing
The gist
Finding a maximal independent set (MIS) in a network means choosing nodes that aren't connected to each other, and none can be added without creating a connection. The authors show that any distributed algorithm working in fewer than about log n divided by log log n rounds can only solve this problem with very low chance for some networks. This confirms that older known algorithms running in about log n rounds are almost as fast as possible. They prove this by constructing special complex networks and carefully analyzing how algorithms behave on them.
Open → 2610.18215v1

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$.

Thu 8 OctInformation Theory
The gist
The Wyner-Ziv problem deals with compressing data when some related information is available to the decoder but not the encoder. The authors improved the understanding of how precisely such compression performs by finding exact second-order terms that describe coding rates more accurately. They showed previous best methods were not always optimal and provided better coding bounds by adapting the compression method depending on the data type. This result helps refine limits on how efficiently data can be compressed in certain settings with side information.
Open → 2610.11998v1

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.

Thu 8 OctLogic in Computer Science
The gist
Deciding if a player can guarantee winning in complex games with many opponents is tough and can require huge computations. The authors developed new methods using a concept called 'antichains' to efficiently find the minimal information a player needs to win such games. They made two algorithms implementing this idea and tested their performance compared to existing methods. Their work helps simplify understanding strategies in multiplayer games where moves happen at the same time.
Open → 2610.11711v1

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.

Wed 7 OctData Structures and AlgorithmsComputational Complexity
The gist
This paper shows that when you change parts of certain directed graphs and try to quickly answer if one part connects to another, there's a fundamental speed limit to how fast this can be done. The researchers improved previous knowledge about these speed limits, showing they're even stricter than known before. Their proof uses advanced ideas from communication theory to handle specific graph problems better. This tells computer scientists that some fast answers for dynamic graphs just aren't possible.
Open → 2610.10904v1

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.

Sun 4 OctNetworking and Internet Architecture
The gist
Controlling large groups of moving objects, like drones or robots working together, can create too much back-and-forth communication because their positions are constantly reported. The authors propose a new method called thermodynamic digital twins that predicts swarm movements using physics ideas and only updates communication when important changes happen. This reduces unnecessary communication while still keeping the control accurate. Their system was tested in simulations showing it balances tracking accuracy and communication cost well, and works better with delays in control.
Open → 2610.05050v1

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.

Thu 1 OctInformation Theory
The gist
Sending messages through unknown communication channels is common, and classical coding methods can handle this well while keeping reliability high. This paper shows that for channels involving quantum outputs, such universal methods cannot always reach the best possible reliability. The reason is that ignorance about how quantum outputs might be rotated interferes with decoding. The authors identify precise mathematical limits and construct coding schemes that achieve the best possible reliability allowed without detailed channel knowledge.
Open → 2610.01941v1

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.

Tue 29 SeptLogic in Computer Science
The gist
The paper presents a simplified and more general version of Gaifman's Theorem, which helps break down complex logical statements into local parts without increasing their complexity. The authors extend this result beyond ordinary first-order logic to more expressive logical systems that include counting and weighted elements. This new theorem aids in understanding and deciding logical properties efficiently on large but sparse data structures. It also provides a clearer path toward faster algorithms for complex logical queries in these settings.
Open → 2609.37337v1

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.

Mon 28 SeptLogic in Computer ScienceFormal Languages and Automata TheoryProgramming Languages
The gist
Modern distributed computer systems send messages without waiting for receivers to be ready, which is called asynchronous communication. The authors look at a way to reverse these message actions so that you can undo steps in a process without breaking important cause-and-effect links. They created a new version of a process algebra called CCS that models asynchronous messaging and then extended it to be reversible while keeping track of message events. Their work ensures that reversing actions respects the original order and dependencies of messages, which is helpful for analyzing and debugging distributed software.
Open → 2609.34925v1

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.

Mon 28 SeptDistributed, Parallel, and Cluster ComputingData Structures and Algorithms
The gist
The authors focused on proving that certain problems in distributed computing need more time to solve when computers work randomly. They showed that a classic technique to explain hard problems, called round elimination, can actually be used in a broader way than before. By changing how errors in algorithms are measured, they found stronger limits on how fast distributed algorithms can run. This means many graph problems, like finding matchings, require at least about the square root of the logarithm of the network size in communication rounds.
Open → 2609.34753v1

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.

Wed 23 SeptInformation Theory
The gist
Communicating data in short chunks can lead to different types of problems: sometimes the receiver gets confused and picks the wrong message, and sometimes it just gives up and says it lost the message. The authors show that these two failure types can be separated and accurately bounded using a geometric approach, instead of lumping them together. This helps provide real mathematical support for treating lost messages as erasures in communication protocols. They also explore how often the system mistakenly believes an idle message was sent, which leads to a new simple channel model useful for designing reliable communication systems.
Open → 2609.27519v1

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.

Wed 16 SeptInformation Theory
The gist
Communicating over a channel where some bits get randomly deleted is a hard problem, and exactly how much information you can send without errors is unknown. The authors provide a highly accurate estimate of this maximum reliable rate, called the capacity, with an error smaller than one hundredth of a bit per bit sent. They use computer-assisted proofs combining clever mathematical bounds and numerical checks over every possible deletion probability. Their approach also includes complete computational details and code so others can verify or build on their work.
Open → 2609.19412v1

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.

Wed 16 SeptData Structures and AlgorithmsComputational Complexity
The gist
This paper looks at how computers store and quickly access information from a special kind of table called a matrix. The authors study how much extra memory and how many checks to memory spots are needed to answer certain questions about the matrix after some preparation. They introduce a new model that helps prove limits on these trade-offs, showing when it’s impossible to have both very little extra memory and very fast answers. Their findings also provide evidence supporting a longstanding idea about how much space certain data tasks require.
Open → 2609.18024v1

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.

Tue 15 SeptComputer Science and Game TheoryDiscrete Mathematics
The gist
This work studies how inefficient networks can become when individuals create connections selfishly, focusing on a game where players try to minimize their longest distance to others. The authors found that, contrary to some hopes, the inefficiency can grow quite fast as the network gets larger when the cost to add an edge is exactly one. They built specific network examples to show this large inefficiency, and also showed that when edge costs shrink fast enough, the inefficiency remains bounded. This helps to better understand how selfish behavior influences network quality in such settings.
Open → 2609.17395v1

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}$.

Wed 9 SeptHardware Architecture
The gist
Data errors happen during AI communication, but not all errors are equally serious. The authors developed SAGE, a method that recognizes which errors matter most and fixes only those, speeding up recovery. SAGE also adapts to where errors occur, making the whole system faster and more reliable. This approach reduces delays and keeps AI data quality higher during movement.
Open → 2609.10126v1