Computationally Efficient Collaborative Communication Via Regularity-Based Coarsening

• URL: http://arxiv.org/abs/2608.05327v1
• Date: Wed, 05 Aug 2026 18:34:19 GMT
• Title: Computationally Efficient Collaborative Communication Via Regularity-Based Coarsening
• Abstract summary: We show a protocol achieving utility at least $- using only $2mathcal O(CC_(G))/2$ bits of communication.<n>We note that our results strictly weaken the assumptions required by prior work in the multi-agent information aggregation literature.
• Score: 26.60272178029048
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 $\mathrm{poly}(n, m, 1/ε)$ runtime that designs a protocol achieving utility at least $α-ε$ using only $2^{\mathcal 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=\mathrm{NP}$, no polynomial-time algorithm can in general find optimal protocols using fewer than $2^{CC_α(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.

Related papers

• Optimal entanglement-assisted source coding under a balanced-difference promise [0.0]
  Entanglement can reduce the communication required for coding tasks, but establishing the minimum achievable cost is essential to understanding its limits.<n>We address this question in a zero-error source-coding task where Alice receives a word and Bob knows an unordered pair of candidates containing it.<n>We prove that the task requires exactly $n$ messages when $(q-1)ell$ is even and two messages when it is odd.
  arXiv  Detail & Related papers  (2026-09-14T15:43:27Z)
• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  We study tradeoff between solution quality and stability when elements arrive over time.<n>Our algorithm has a future implementation for rational oracle$ with $O(varepsilon-1)$ recourse and separate the existence of universal-price certificates from their efficient algorithms.
  arXiv  Detail & Related papers  (2026-09-09T10:13:43Z)
• Exponentially Fewer-Server PIR from Sparser $S$-Decoding Polynomials [2.5782420501870296]
  We show that for any constant $s$ there exists an $s$-server private information retrieval protocol.<n>Our number-theoretic conjecture is implied by existing conjectures.
  arXiv  Detail & Related papers  (2026-07-24T06:59:30Z)
• Efficient Fuzzy Private Set Intersection from Secret-shared OPRF [41.88845480337768]
  Fuzzy PSI (FPSI) is a PSI variant where the receiver learns the items $q in Q$ for which there exists some $w in W$ under a given distance metric.<n>We propose efficient FPSI protocols for $L_p in [1, infty]$ distance metrics.<n>Our protocols achieve linear communication and computation complexity in the set sizes $m,n$, the dimension $d$, and the distance threshold $$.
  arXiv  Detail & Related papers  (2026-04-16T11:51:25Z)
• Nearly-Optimal Consensus Tolerating Adaptive Omissions: Why is a Lot of Randomness Needed? [4.465134753953128]
  We study the problem of reaching agreement in a synchronous distributed system by $n$ autonomous parties, when the communication links from/to faulty parties can omit messages. We design a randomized algorithm that works in $O(sqrtnlog2 n)$ rounds and sends $O(n2log3 n)$ communication bits. We prove that no MC algorithm can work in less than $Omega(fracn2maxR,nlog n)$ rounds if it uses less than $O(R)$ calls to
  arXiv  Detail & Related papers  (2024-05-08T02:17:10Z)
• Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages [63.366380571397]
  We study the problem of private vector mean estimation in the shuffle model of privacy where $n$ users each have a unit vector $v(i) inmathbbRd$. We propose a new multi-message protocol that achieves the optimal error using $tildemathcalOleft(min(nvarepsilon2,d)right)$ messages per user.
  arXiv  Detail & Related papers  (2024-04-16T00:56:36Z)
• A Quantum Approach For Reducing Communications in Classical Secure Computations with Long Outputs [2.3465488122819123]
  We study the classical cryptographic problem that two parties would like to perform secure computations with long outputs.<n>In this work, we first design a quantum cryptographic protocol that achieves secure function sampling with approximate security.
  arXiv  Detail & Related papers  (2023-10-08T16:07:46Z)
• Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation [77.09836892653176]
  We study multi-agent reinforcement learning in the setting of episodic Markov decision processes. We propose a provably efficient algorithm based on value that enable asynchronous communication. We show that a minimal $Omega(dM)$ communication complexity is required to improve the performance through collaboration.
  arXiv  Detail & Related papers  (2023-05-10T20:29:29Z)
• Non-local computation of quantum circuits with small light cones [0.0]
  Port-based teleportation costs much less entanglement when done only on a small number of qubits at a time. We give an explicit class of unitaries for which our protocol's entanglement cost scales better than any known protocol.
  arXiv  Detail & Related papers  (2022-03-18T18:00:06Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  One of its most powerful and successful modalities approximates every distribution to an $ell$ distance essentially at most a constant times larger than its closest $t$-piece degree-$d_$. We provide a method that estimates this number near-optimally, hence helps approach the best possible approximation.
  arXiv  Detail & Related papers  (2022-02-15T03:49:28Z)
• Nearly Optimal Policy Optimization with Stable at Any Time Guarantee [53.155554415415445]
  Policy-based method in citetshani 2020optimistic is only $tildeO(sqrtSAH3K + sqrtAH4K)$ where $S$ is the number of states, $A$ is the number of actions, $H$ is the horizon, and $K$ is the number of episodes, and there is a $sqrtSH$ gap compared with the information theoretic lower bound $tildeOmega(sqrtSAH
  arXiv  Detail & Related papers  (2021-12-21T01:54:17Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  We study the setup where each of $n$ users holds an element from a discrete set. The goal is to count the number of distinct elements across all users.
  arXiv  Detail & Related papers  (2020-09-21T04:13:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.