Ultra-Resilient Superimposed Codes: Near-Optimal Construction and Applications Article Swipe

PDF

Gianluca De Marco , Dariusz R. Kowalski ·

YOU? · · 2025 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2506.13489

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$ others, enabling unique identification of codewords within any group of $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$ 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$. % 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.

Related Topics

List Of Http Status Codes

List Of Dialling Codes In The United Kingdom

Area Codes 678, 470, And 943

List Of Dialling Codes In Brazil

Recycling Codes

Area Codes 845 And 329

Postal Codes In The Netherlands

Postal Codes In Poland

Postal Codes In Vietnam

Postal Codes In Belgium

Area Codes 201 And 551

Postal Codes In Taiwan

Concepts

No concepts available.

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2506.13489
PDF: https://arxiv.org/pdf/2506.13489
OA Status: green
OpenAlex ID: https://openalex.org/W4415108949

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4415108949

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2506.13489

Digital Object Identifier
Title: Ultra-Resilient Superimposed Codes: Near-Optimal Construction and Applications

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2025

Year of publication
Publication date: 2025-06-16

Full publication date if available
Authors: Gianluca De Marco, Dariusz R. Kowalski

List of authors in order
Landing page: https://arxiv.org/abs/2506.13489

Publisher landing page
PDF URL: https://arxiv.org/pdf/2506.13489

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2506.13489

Direct OA link when available
Cited by: 0

Total citation count in OpenAlex

Full payload

id	https://openalex.org/W4415108949
doi	https://doi.org/10.48550/arxiv.2506.13489
ids.doi	https://doi.org/10.4230/lipics.icalp.2025.65
ids.openalex	https://openalex.org/W4415108949
fwci
type	preprint
title	Ultra-Resilient Superimposed Codes: Near-Optimal Construction and Applications
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T11130
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9868999719619751
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1702
topics[0].subfield.display_name	Artificial Intelligence
topics[0].display_name	Coding theory and cryptography
topics[1].id	https://openalex.org/T11321
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9535999894142151
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1705
topics[1].subfield.display_name	Computer Networks and Communications
topics[1].display_name	Error Correcting Code Techniques
topics[2].id	https://openalex.org/T10558
topics[2].field.id	https://openalex.org/fields/22
topics[2].field.display_name	Engineering
topics[2].score	0.9312999844551086
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/2208
topics[2].subfield.display_name	Electrical and Electronic Engineering
topics[2].display_name	Advancements in Semiconductor Devices and Circuit Design
is_xpac	False
apc_list
apc_paid
language	en
locations[0].id	pmh:oai:arXiv.org:2506.13489
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2506.13489
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2506.13489
locations[1].id	doi:10.48550/arxiv.2506.13489
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license	cc-by
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id	https://openalex.org/licenses/cc-by
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2506.13489
locations[2].id	doi:10.4230/lipics.icalp.2025.65
locations[2].is_oa	True
locations[2].source.id	https://openalex.org/S7407052059
locations[2].source.type	repository
locations[2].source.is_oa	False
locations[2].source.issn_l
locations[2].source.is_core	False
locations[2].source.is_in_doaj	False
locations[2].source.display_name	Dagstuhl Research Online Publication Server
locations[2].source.host_organization
locations[2].source.host_organization_name
locations[2].license	cc-by
locations[2].pdf_url
locations[2].version
locations[2].raw_type
locations[2].license_id	https://openalex.org/licenses/cc-by
locations[2].is_accepted	False
locations[2].is_published
locations[2].raw_source_name
locations[2].landing_page_url	https://doi.org/10.4230/lipics.icalp.2025.65
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5087104329
authorships[0].author.orcid	https://orcid.org/0000-0002-1204-0646
authorships[0].author.display_name	Gianluca De Marco
authorships[0].author_position	first
authorships[0].raw_author_name	De Marco, Gianluca
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5101948468
authorships[1].author.orcid	https://orcid.org/0000-0002-1316-7788
authorships[1].author.display_name	Dariusz R. Kowalski
authorships[1].author_position	last
authorships[1].raw_author_name	Kowalski, Dariusz R.
authorships[1].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2506.13489
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-13T00:00:00
display_name	Ultra-Resilient Superimposed Codes: Near-Optimal Construction and Applications
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T11130
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9868999719619751
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1702
primary_topic.subfield.display_name	Artificial Intelligence
primary_topic.display_name	Coding theory and cryptography
cited_by_count	0
locations_count	3
best_oa_location.id	pmh:oai:arXiv.org:2506.13489
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2506.13489
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2506.13489
primary_location.id	pmh:oai:arXiv.org:2506.13489
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2506.13489
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2506.13489
publication_date	2025-06-16
publication_year	2025
referenced_works_count	0
abstract_inverted_index.%	180
abstract_inverted_index.A	0
abstract_inverted_index.a	4, 87, 100, 139
abstract_inverted_index.We	81, 149, 181
abstract_inverted_index.by	98, 209
abstract_inverted_index.in	18, 44, 68, 76, 145, 193, 219
abstract_inverted_index.is	3, 16, 138
abstract_inverted_index.no	14
abstract_inverted_index.of	6, 22, 29, 34, 90, 110, 131, 141, 155, 173, 176, 190, 213
abstract_inverted_index.on	61
abstract_inverted_index.to	53, 107, 127
abstract_inverted_index.$k$	24, 130
abstract_inverted_index.all	168
abstract_inverted_index.and	50, 70, 79, 105, 116, 215
abstract_inverted_index.any	23, 32, 128, 146
abstract_inverted_index.are	38, 74
abstract_inverted_index.art	192
abstract_inverted_index.for	206
abstract_inverted_index.new	88
abstract_inverted_index.not	143
abstract_inverted_index.our	184, 201
abstract_inverted_index.sum	21
abstract_inverted_index.the	11, 19, 94, 151, 174, 188, 191
abstract_inverted_index.two	108, 211
abstract_inverted_index.$k$.	35, 179
abstract_inverted_index.This	137
abstract_inverted_index.code	2
abstract_inverted_index.data	51
abstract_inverted_index.from	47
abstract_inverted_index.less	165
abstract_inverted_index.rely	60
abstract_inverted_index.that	13, 92, 183
abstract_inverted_index.time	204
abstract_inverted_index.with	10, 42, 157, 164
abstract_inverted_index.Codes	85
abstract_inverted_index.URSCs	122, 156, 185
abstract_inverted_index.areas	45
abstract_inverted_index.class	89
abstract_inverted_index.codes	37, 59, 91, 202
abstract_inverted_index.first	152
abstract_inverted_index.group	33
abstract_inverted_index.local	207
abstract_inverted_index.prior	135, 171
abstract_inverted_index.state	189
abstract_inverted_index.their	66
abstract_inverted_index.tools	41
abstract_inverted_index.types	109
abstract_inverted_index.where	200
abstract_inverted_index.which	73
abstract_inverted_index.binary	7
abstract_inverted_index.common	75
abstract_inverted_index.cyclic	114
abstract_inverted_index.modern	77
abstract_inverted_index.nearly	210
abstract_inverted_index.number	129, 175
abstract_inverted_index.orders	212
abstract_inverted_index.reduce	203
abstract_inverted_index.shifts	115
abstract_inverted_index.strict	62
abstract_inverted_index.unique	27
abstract_inverted_index.vector	15
abstract_inverted_index.within	31
abstract_inverted_index.Boolean	20
abstract_inverted_index.advance	187
abstract_inverted_index.beeping	198
abstract_inverted_index.bitwise	118
abstract_inverted_index.channel	221
abstract_inverted_index.classic	95
abstract_inverted_index.exhibit	123
abstract_inverted_index.extends	93
abstract_inverted_index.general	166
abstract_inverted_index.length,	159
abstract_inverted_index.others,	25
abstract_inverted_index.partial	117
abstract_inverted_index.provide	150
abstract_inverted_index.ranging	46
abstract_inverted_index.systems	78
abstract_inverted_index.vectors	8
abstract_inverted_index.without	134, 169
abstract_inverted_index.(URSCs),	86
abstract_inverted_index.(flips).	120
abstract_inverted_index.However,	56
abstract_inverted_index.achieved	144
abstract_inverted_index.adapting	125
abstract_inverted_index.enabling	26
abstract_inverted_index.ensuring	99
abstract_inverted_index.limiting	65
abstract_inverted_index.multiple	194
abstract_inverted_index.previous	147, 162
abstract_inverted_index.property	12, 104
abstract_inverted_index.stronger	101
abstract_inverted_index.alignment	63
abstract_inverted_index.arbitrary	113
abstract_inverted_index.broadcast	208
abstract_inverted_index.classical	57
abstract_inverted_index.codewords	30, 133
abstract_inverted_index.computing	49
abstract_inverted_index.contained	17
abstract_inverted_index.features,	167
abstract_inverted_index.framework	97
abstract_inverted_index.including	196
abstract_inverted_index.introduce	82
abstract_inverted_index.isolation	103
abstract_inverted_index.knowledge	172
abstract_inverted_index.networks,	199
abstract_inverted_index.requiring	170
abstract_inverted_index.retrieval	52
abstract_inverted_index.codewords'	102
abstract_inverted_index.codewords,	178
abstract_inverted_index.collection	5
abstract_inverted_index.complexity	205
abstract_inverted_index.concurrent	132, 177
abstract_inverted_index.contention	217
abstract_inverted_index.corruption	119
abstract_inverted_index.knowledge.	136
abstract_inverted_index.magnitude,	214
abstract_inverted_index.properties	142
abstract_inverted_index.resilience	106
abstract_inverted_index.resolution	218
abstract_inverted_index.seamlessly	126
abstract_inverted_index.(codewords)	9
abstract_inverted_index.adversarial	111
abstract_inverted_index.combination	140
abstract_inverted_index.demonstrate	182
abstract_inverted_index.distributed	48
abstract_inverted_index.fault-prone	71
abstract_inverted_index.generalized	216
abstract_inverted_index.Superimposed	36, 84
abstract_inverted_index.applications	43
abstract_inverted_index.assumptions,	64
abstract_inverted_index.asynchronous	69
abstract_inverted_index.construction	154
abstract_inverted_index.foundational	39
abstract_inverted_index.multi-access	220
abstract_inverted_index.near-optimal	158
abstract_inverted_index.superimposed	1, 58, 96
abstract_inverted_index.Additionally,	121
abstract_inverted_index.applications,	195
abstract_inverted_index.applications.	80
abstract_inverted_index.combinatorial	40
abstract_inverted_index.construction.	148
abstract_inverted_index.constructions	163
abstract_inverted_index.effectiveness	67
abstract_inverted_index.environments,	72
abstract_inverted_index.outperforming	161
abstract_inverted_index.significantly	160, 186
abstract_inverted_index.uncoordinated	197
abstract_inverted_index.universality,	124
abstract_inverted_index.communication.	55, 222
abstract_inverted_index.fault-tolerant	54
abstract_inverted_index.identification	28
abstract_inverted_index.perturbations:	112
abstract_inverted_index.Ultra-Resilient	83
abstract_inverted_index.polynomial-time	153
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	2
citation_normalized_percentile