Set Reconciliation (Q7361348)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
AFP entry Set_Reconciliation
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Set Reconciliation |
AFP entry Set_Reconciliation |
Statements
3 December 2025
0 references
Paul Hofmeier
0 references
Emin Karayel
0 references
Set Reconciliation (English)
0 references
This entry formally verifies the set reconciliation algorithm with nearly optimal communication complexity, due to Y. Minsky et al. [1]. The algorithm allows two communication partners, who have a similar pair of sets to reconcile them while using messages of nearly optimal size, proportional to a bound on the maximum symmetric difference between the sets. The formalization also introduces an optimization, which reduces the communication complexity even further compared to the original publication.
0 references
