Ultra-Resilient Superimposed Codes: Near-Optimal Construction and Applications
Gianluca De Marco, Dariusz R. Kowalski · 2025
Read Ultra-Resilient Superimposed Codes: Near-Optimal Construction and Applications by Gianluca De Marco, Dariusz R. Kowalski (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-13489.txt.
Introduction
Gianluca De Marco and Dariusz Kowalski introduce, in 2025, a tougher breed of superimposed codes. Such codes let any member of a small group be identified from the combined pattern of the group, a trick used in data retrieval and fault-tolerant communication. Classic versions break when signals shift in time or bits get flipped.
The new codes survive both cyclic shifts and partial corruption, and they adapt to any group size without being told it in advance. The authors give the first fast construction with near-optimal length. In beeping networks, the codes cut local broadcast time by nearly a hundredfold, with further gains in shared-channel contention tasks.
Catalog record
| CREATOR | Gianluca De Marco, Dariusz R. Kowalski |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 116 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-13489
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Ultra-Resilient Superimposed Codes: Near-Optimal Construction and Applications Gianluca De Marco, Dariusz R. Kowalski Abstract A superimposed code is a collection of binary vectors (codewords) with the property that no vector is contained in the Boolean sum of any k k others, enabling unique identification of codewords within any group of k k . Superimposed codes are foundational combinatorial tools with applications in areas ranging from distributed computing and data retrieval to fault-tolerant communication. However, classical superimposed codes rely on strict alignment assumptions, limiting their effectiveness in asynchronous and fault-prone environments, which are common in modern systems and applications. We introduce Ultra-Resilient Superimposed Codes (URSCs), a new class of codes that extends the classic superimposed framework by ensuring a stronger codewords’ isolation property and resilience to two types of adversarial perturbations: arbitrary cyclic shifts and partial bitwise corruption (flips). Additionally, URSCs exhibit universality, adapting seamlessly to any number k k of concurrent codewords without prior knowledge. This is a combination of properties not achieved in any previous construction. We provide the first polynomial-time construction of URSCs with near-optimal length, significantly outperforming previous constructions with less general features, all without requiring prior knowledge of the number of concurrent codewords, k k . We demonstrate that our URSCs significantly advance the state of the art in multiple applications, including uncoordinated beeping networks, where our codes reduce time complexity for local broadcast by nearly two orders of magnitude, and generalized contention resolution in multi-access channel communication. Keywords: superimposed codes, ultra-resiliency, derandomization, deterministic algorithms, uncoordinated beeping networks, contention resolution. 1 Introduction Superimposed codes , proposed by Kautz and Singleton in 1964 [ 21 ] , are a well-known and widely used class of codes represented by a binary t\times n matrix, where columns correspond to codewords. These codes have a distinctive property: for any subset of k columns from the matrix, and for any column \mathbf{c} within this subset, there exists at least one row where column \mathbf{c} has an entry of 1 while all other columns in the subset have entries of 0. This feature allows for the unique identification of any single column (codeword) within a subset of columns. The significance of superimposed codes cannot be overstated. Over the past six decades, these codes have found applications in an impressively wide range of fields. For instance, they have proven instrumental in information retrieval (see e.g. [ 23 , p. 570] ), pattern matching [ 19 , 30 ] , learning problems [ 2 , 22 ] , wireless and multi-access communication [ 34 , 20 , 5 ] , distributed coloring [ 26 , 29 ] . Despite their broad applicability, classic superimposed codes have a significant limitation: they require perfectly aligned (i.e., fixed) codewords. For example, in wireless distributed communication, this alignment requires synchronization before the codes can be applied. Similarly, in distributed information retrieval, it necessitates the alignment of file descriptor codewords. However, achieving synchronization is often challenging or impractical in many distributed environments, where entities may start using codewords at arbitrary times as they wake up and join the system. Dynamic data retrieval also presents difficulties, as it may involve data arriving out of order. The lack of synchronization creates a difficulty in defining a meaningful product of two codes. Other limitations arise from a limited capacity to handle data corruption. Finally, existing codes assume that the number of superimposed codewords, k , is known. However, some applications may not provide this in advance, and standard estimation techniques—such as doubling the estimate of k —are ineffective, as consecutive code estimates can overlap due to arbitrary misalignments of codewords. The purpose of the present work is to introduce and efficiently construct new superimposed codes that simultaneously address all the above limitations. We provide a near-optimal solution that significantly outperforms prior codes, which were designed to ensure only some or weaker properties, and demonstrate usefulness of new code’s properties in various applications. 1.1 Our contributions and comparison with previous works Before presenting the formal description in Section 2 (Definition 2 ), we will provide a high-level overview of our codes. We begin with the classic definition of superimposed codes, followed by an outline of the properties of our codes, including both the newly introduced and previously established properties. We will then review the relevant literature related to our codes and compare their performance to prior results. Finally, we will conclude with a discussion on how these codes can enhance performance in pertinent distributed problems, particularly in beeping networks and multiple-access channels, as well as in other contexts. Definition 1 (Classic definition) . A (k,n) -superimposed code is formally defined as a t\times n binary matrix \mathbf{M} such that the following property holds: ( {\mathcal{I}} ) For any k -tuple of columns of \mathbf{M} and for any column \mathbf{c} of the given k -tuple, there is a row 0\leq i<t such that column \mathbf{c} has 1 in row i and all remaining k-1 columns of the k -tuple have all 0 in row i . The columns of matrix \mathbf{M} are called codewords and their length t is called the code length. 1.1.1 Ultra-Resilient Superimposed Codes (URSC) Our newly proposed ultra-resilient superimposed codes represent a substantial generalization of the classic definition, designed to provide robust performance without requiring prior knowledge of the number k of superimposed codes. We start from the following enhanced version of property {\mathcal{I}} , which ensures a better isolation of codewords; consequently, as shown in Section 4 (Algorithm 2 and Lemma 15 ), it allows to implement a meaningful product of codes even in the presence of arbitrary codeword misalignment and bit corruption. Isolation property: ( {\mathcal{I}^{\prime}} ) For any k -tuple of columns of \mathbf{M} and any column \mathbf{c} of this k -tuple, there exists a row 0\leq i<t such that column \mathbf{c} has a 1 in row i , while all other k-1 columns of the k -tuple have 0 in rows (i-1)\bmod t , i , and (i+1)\bmod t . At a high level, the ultra-resilient capability of our codes simultaneously ensures the following: (a) Shift resilience: Even if each codeword undergoes independent and arbitrary cyclic shifts, property {\mathcal{I}^{\prime}} is still preserved. This resilience is particularly effective in uncoordinated settings where computational entities can join the system at arbitrary times (asynchronous activations). (b) Flip resilience: Property {\mathcal{I}^{\prime}} remains intact even if a fraction 1-\alpha of unique occurrences of ones in each codeword can be flipped (the classic setting is obtained for \alpha=1 ). This ensures robust performance under adversarial jamming in dynamic, asynchronous environments. (c) Universality: The construction and application of these codes do not require prior knowledge of the parameter k , the number of concurrently active codewords. This intrinsic feature enables their applicability across dynamic and uncertain settings where k may vary or remain unknown. Note: Our codes ensure that flip resilience is fully integrated with shift resilience, so that these properties work together to reinforce robustness. Specifically, flip resilience is maintained under arbitrary cyclic shifts, meaning that for any shifted configuration, the isolation property \mathcal{I^{\prime}} holds even if a fraction 1-\alpha of ones in each codeword is flipped. This combined ultra-resilience provides robust protection in dynamic and adversarial environments, where both positional misalignments