General Convex Agreement with Near-Optimal Communication
Marc Dufay, Diana Ghinea, Anton Paramonov · 2026
Read General Convex Agreement with Near-Optimal Communication by Marc Dufay, Diana Ghinea, Anton Paramonov (2026) 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-2602-21411.txt.
Description
Marc Dufay and two co-authors close a gap in convex agreement. Convex agreement is a stronger form of Byzantine agreement. Honest parties must agree on an output inside the convex hull of their inputs. That rule fits aggregation jobs like robust learning and sensor fusion. But past protocols for general convexity spaces needed at least order L times n squared bits of communication.
Their deterministic synchronous protocols cut that cost to near-optimal levels in the long-message regime. Finite convexity spaces need order L times n log n bits. Euclidean spaces need order L times n to the one-plus-small power. Round complexity is optimal at order n. With a known input-length bound they reach resilience near t below n over the Helly number. The key tool is extractor graphs assigning parties to committees robustly against adaptive adversaries.
Catalog record
| CREATOR | Marc Dufay, Diana Ghinea, Anton Paramonov |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 131 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-21411