# Computationally Efficient Collaborative Communication Via Regularity-Based Coarsening

arXiv: https://arxiv.org/abs/2608.05327 · HTML: https://mlsanity.com/paper/2608.05327/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 59 references that are in the map.
- First posted on arXiv 5 Aug 2026.

## Builds on (most cited first, 5 of 5)

- [Omnipredictors](https://mlsanity.com/paper/2109.05389/) (2021)
- [Loss Minimization through the Lens of Outcome Indistinguishability](https://mlsanity.com/paper/2210.08649/) (2022)
- [From Pseudorandomness to Multi-Group Fairness and Back](https://mlsanity.com/paper/2301.08837/) (2023)
- [False Consensus, Information Theory, and Prediction Markets](https://mlsanity.com/paper/2206.02993/) (2022)
- [NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing](https://mlsanity.com/paper/2508.05597/) (2025)

## Abstract (arXiv)

Our results show that the existence of a short high-utility protocol already suffices for efficient communication. In particular, in a game with n possible observations and m actions: (1) For any achievable target utility α, we give an algorithm with poly(n, m, 1/ε) runtime that designs a protocol achieving utility at least α-ε using only 2mathcal O(CCα(G))/ε2 bits of communication. Here, CCα(G) is the minimum number of bits used by any protocol, even a computationally inefficient one, to achieve utility α. (2) We prove that this exponential dependence on CCα(G) is tight up to a constant. That is, unless mathrm P=NP, no polynomial-time algorithm can in general find optimal protocols using fewer than 2CCα(G) -2 bits. We note that our results strictly weaken the assumptions required by prior work in the multi-agent information aggregation literature, filling a gap that had remained elusive even for games with constant CCα(G). In particular, prior guarantees for agreement-based information aggregation rely on structural assumptions such as informational substitutes or weak learnability. We show that these assumptions already imply CCα(G) = O(1) and are therefore more restrictive conditions than required by our protocol to succeed. On a technical level, our results involve a novel strengthening of the Frieze-Kannan weak regularity lemma and yield the following powerful polynomial-time transformation tool: for every communication game G, it constructs a game hat G that is a coarsening of the agents' observation spaces into constant-size partitions, such that G and hat G are indistinguishable with respect to every short communication protocol. This coarsening theorem is the engine behind our algorithm and may be of independent interest.