Fugu-MT 論文翻訳(概要): Computationally Efficient Collaborative Communication Via Regularity-Based Coarsening

論文の概要: Computationally Efficient Collaborative Communication Via Regularity-Based Coarsening

arxiv url: http://arxiv.org/abs/2608.05327v1
Date: Wed, 05 Aug 2026 18:34:19 GMT
ステータス: 翻訳完了
システム内更新日: 2026-08-07 17:43:06.658751
Title: Computationally Efficient Collaborative Communication Via Regularity-Based Coarsening
Title（参考訳）: 正規性に基づくコラボレーティブコミュニケーションの計算効率
Abstract要約: 我々は,少なくとも$-を達成するためのプロトコルを,2$mathcal O(CC_(G))/2$の通信ビットのみを用いて示す。本研究の結果は,マルチエージェント情報集約文学における先行研究で要求される仮定を厳格に弱めることに留意する。
参考スコア（独自算出の注目度）: 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.
Abstract（参考訳）: この結果から,高速通信に有効な短効性プロトコルがすでに存在することが示唆された。特に、$n$の観測と$m$のアクションを持つゲームでは、(1) 達成可能な任意の目的ユーティリティ$α$に対して、$\mathrm{poly}(n, m, 1/ε)$のランタイムを持つアルゴリズムを与える。ここで、$CC_α(G)$は、どんなプロトコルでも使われる最小のビット数であり、計算的に非効率なものであっても、ユーティリティ$α$を達成するために使われる。 2) CC_α(G)$ に対する指数的依存は定数まで厳密であることを示す。つまり、$\mathrm P=\mathrm{NP}$ でない限り、多項式時間アルゴリズムは一般には 2^{CC_α(G) -2}$ ビット未満で最適なプロトコルを見つけることはできない。本研究の結果は,マルチエージェント情報集約文学における先行研究で要求される仮定を厳格に弱め,一定の$CC_α(G)$のゲームであっても解答が残っていたギャップを埋めることに注意する。特に、合意に基づく情報集約の事前保証は、情報代行や弱い学習可能性といった構造的仮定に依存している。これらの仮定は、既に$CC_α(G) = O(1)$であり、我々のプロトコルが成功するために必要な条件よりも制限的な条件であることを示す。技術的レベルでは,Fryeze-Kannan弱正則性の補題を新たに強化し,次の強力な多項式時間変換ツールを生成する。すべての通信ゲームに対して$G$に対して,エージェントの観測空間を一定の大きさのパーティションにまとめるゲーム$\hat G$を構築し,例えば,$G$と$\hat G$は,すべての短通信プロトコルに関して区別不能である。この粗い定理は我々のアルゴリズムの背後にあるエンジンであり、独立した関心を持つかもしれない。

関連論文リスト

Optimal entanglement-assisted source coding under a balanced-difference promise [0.0]
絡み合いは、コーディングタスクに必要なコミュニケーションを減らすことができるが、その限界を理解するためには、達成可能な最小コストの確立が不可欠である。我々は、Aliceが単語を受信し、Bobはその単語を含む無秩序な候補のペアを知っているゼロエラーソースコーディングタスクでこの問題に対処する。我々は、$(q-1)ell$が偶数であるとき、そのタスクに正確に$n$メッセージが必要であることを証明している。
論文参考訳（メタデータ） (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]
我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
論文参考訳（メタデータ） (2026-09-09T10:13:43Z)
Exponentially Fewer-Server PIR from Sparser $S$-Decoding Polynomials [2.5782420501870296]
一定の$s$に対して、$s$サーバのプライベート情報検索プロトコルが存在することを示す。我々の数論予想は既存の予想によって示唆される。
論文参考訳（メタデータ） (2026-07-24T06:59:30Z)
Efficient Fuzzy Private Set Intersection from Secret-shared OPRF [41.88845480337768]
Fuzzy PSI (FPSI) は、受信者がQ$で$qを学習するPSI変種であり、W$に約$wが存在する。本稿では, [1, infty]$ distance における$L_p に対する効率的な FPSI プロトコルを提案する。我々のプロトコルは、集合サイズ$m,n$、次元$d$、距離しきい値$$で線形通信と計算の複雑さを実現する。
論文参考訳（メタデータ） (2026-04-16T11:51:25Z)
Nearly-Optimal Consensus Tolerating Adaptive Omissions: Why is a Lot of Randomness Needed? [4.465134753953128]
同期分散システムにおいて,通信リンクから障害当事者への通信がメッセージの送信を省略できる場合,$n$の自律的パーティによる合意に達するという問題について検討する。我々は、$O(sqrtnlog2 n)$ラウンドで動作し、$O(n2log3 n)$通信ビットを送信するランダム化アルゴリズムを設計する。 MCアルゴリズムが$O(R)$呼び出しを使用する場合、$Omega(fracn2maxR,nlog n)$ラウンドで動作しないことを示す。
論文参考訳（メタデータ） (2024-05-08T02:17:10Z)
Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages [63.366380571397]
本稿では,プライバシのシャッフルモデルにおけるプライベートベクトル平均推定の問題について検討する。我々は,$tildemathcalOleft(min(nvarepsilon2,d)right)$ message per users を用いて,最適なエラーを実現する新しいマルチメッセージプロトコルを提案する。
論文参考訳（メタデータ） (2024-04-16T00:56:36Z)
A Quantum Approach For Reducing Communications in Classical Secure Computations with Long Outputs [2.3465488122819123]
我々は、2つの当事者が長い出力でセキュアな計算を行いたいという古典的な暗号問題について研究する。本研究では,セキュリティを近似したセキュアな関数サンプリングを実現するために,まず量子暗号プロトコルを設計する。
論文参考訳（メタデータ） (2023-10-08T16:07:46Z)
Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation [77.09836892653176]
マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
論文参考訳（メタデータ） (2023-05-10T20:29:29Z)
Non-local computation of quantum circuits with small light cones [0.0]
ポートベースのテレポーテーションは、一度に少数の量子ビットでのみ行われる場合、はるかに少ない絡み合いになる。我々は、プロトコルの絡み合いコストが既知のプロトコルよりも良くスケールする、明示的なユニタリのクラスを提供する。
論文参考訳（メタデータ） (2022-03-18T18:00:06Z)
TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。本稿では,この数値をほぼ最適に推定する手法を提案する。
論文参考訳（メタデータ） (2022-02-15T03:49:28Z)
Nearly Optimal Policy Optimization with Stable at Any Time Guarantee [53.155554415415445]
citetshani 2020optimisticのポリシーベースのメソッドは、$tildeO(sqrtSAH3K + sqrtAH4K)$である。$S$は状態の数、$A$はアクションの数、$H$は地平線、$K$はエピソードの数、$sqrtSH$は情報理論の下限の$tildeOmega(sqrtSAH)と比べてギャップがある。
論文参考訳（メタデータ） (2021-12-21T01:54:17Z)
On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
論文参考訳（メタデータ） (2020-09-21T04:13:34Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。