論文の概要: Tight Information Complexity of the Coin Problem in the Broadcast Model

• arxiv url: http://arxiv.org/abs/2608.02776v1
• Date: Mon, 03 Aug 2026 18:21:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-05 15:30:22.915912
• Title: Tight Information Complexity of the Coin Problem in the Broadcast Model
• Title（参考訳）: 放送モデルにおけるコイン問題の高次情報複雑度
• Authors: Hadi Kazemi, Varun Jog,
• Abstract要約: 放送中の$mathrmBer()$と$mathrmBer()$の分散テスト、あるいは共有ブラックボードモデルについて検討する。 一定の優位性を持つプロトコルに対しては、各ペア$$に対して、任意の仮説の下での情報複雑性を普遍的な定数因子まで特徴づける。
• 参考スコア（独自算出の注目度）: 0.21485350418225238
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study distributed testing of $\mathrm{Ber}(α)$ versus $\mathrm{Ber}(β)$ in the broadcast, or shared-blackboard, model. For protocols with constant advantage, we characterise up to universal constant factors the information complexity under either hypothesis for every pair $β<α$. The characterisation shows that the two information costs can be quite different and identifies three parameter regimes, with optimal protocols based respectively on clean samples, a noisy binary symmetric channel, and an asymmetric $Z$-channel. The lower bounds rely on a novel mixed Hellinger--Jensen--Shannon inequality that may be of independent interest. We also characterise the constant-advantage information complexity of testing arbitrary discrete distributions via an optimisation problem over channels, and show that binary-output channels suffice. We obtain bounds for bounded likelihood-ratio distributions, and give general upper bounds in terms of $χ^2$ divergence. As applications, we recover the broadcast-model set-disjointness lower bound, and derive stronger lower bounds in the multi-pass streaming setting for some problems considered in prior work.
• Abstract（参考訳）: 放送や共有黒板モデルにおいて,$\mathrm{Ber}(α)$対$\mathrm{Ber}(β)$の分散テストについて検討した。 一定の優位性を持つプロトコルに対しては、任意のペアの$β<α$に対して、任意の仮説の下での情報複雑性を普遍的な定数因子まで特徴づける。 キャラクタリゼーションは2つの情報コストが全く異なる可能性を示し、クリーンなサンプル、ノイズの多い二値対称チャネル、非対称な$Z$チャネルに基づく最適なプロトコルを持つ3つのパラメータ規則を識別する。 下限はヘリンガー--ジェンセン-シャノンの不等式で、これは独立した関心を持つ可能性がある。 また、チャネル上の最適化問題を通じて任意の離散分布をテストする場合の定常アドバンテージ情報複雑性を特徴付けるとともに、バイナリ出力チャネルが十分であることを示す。 有界な確率比分布の有界値を求め、大まかに上界を $ ^2$ の発散の項で与える。 適用例として,放送モデルのセット不整合性低境界を回復し,先行研究で考慮されたいくつかの問題に対して,マルチパスストリーミング設定におけるより強い下位境界を導出する。

関連論文リスト

• Distributed Monogamy of Entanglement limits Quantum Channel Simulation [2.277447144331876]
  分数拡張性を導入し、環境に漏れる量子相関のよりきめ細かな特徴を与える。 例えば、$AB_Bdots B_n$の任意の状態に対して、$B_i$s内の$k leq n/2$系のランダム部分集合からEPRペアを抽出する最大平均確率は、$k/n$である。
  論文  参考訳（メタデータ） (2026-07-09T15:26:41Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。 一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。 グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
  論文  参考訳（メタデータ） (2026-02-26T15:27:53Z)
• Rate optimal learning of equilibria from data [63.14746189846806]
  マルチエージェント・イミテーション・ラーニング(MAIL)における理論的ギャップは,非対話的MAILの限界を特徴づけ,ほぼ最適なサンプル複雑性を持つ最初の対話的アルゴリズムを提示することによって解決する。 インタラクティブな設定では、報酬のない強化学習と対話型MAILを組み合わせたフレームワークを導入し、それをMAIL-WARMというアルゴリズムでインスタンス化する。 我々は,我々の理論を裏付ける数値的な結果を提供し,グリッドワールドのような環境において,行動クローンが学習に失敗する状況を示す。
  論文  参考訳（メタデータ） (2025-10-10T12:28:35Z)
• Semidefinite programming relaxations and debiasing for MAXCUT-based clustering [1.9761774213809036]
  2つのガウス分布を$mathbbRp$で混合して引き出す小さなデータサンプルを$n$で分割する問題を考察する。 グラフ上の最大カットを求めるように定式化された整数二次プログラムの半定値プログラミング緩和を用いる。
  論文  参考訳（メタデータ） (2024-01-16T03:14:24Z)
• Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints [8.261182037130407]
  局所差分プライバシー (LDP) と通信制約の両面から, 単純な二分仮説テストについて検討する。 我々はその結果をミニマックス最適かインスタンス最適かのどちらかとみなす。
  論文  参考訳（メタデータ） (2023-01-09T18:36:49Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。 次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。 我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
  論文  参考訳（メタデータ） (2022-02-23T16:10:23Z)
• Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
  集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。 $varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。 この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
  論文  参考訳（メタデータ） (2021-10-24T04:03:00Z)
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization [68.8204255655161]
  本稿では,Gorbunov et al (2021) の MARINA 法が,理論的な通信複雑性の観点から最先端の手法とみなすことができることを示す。 MARINAの理論は、古典的な独立圧縮機設定を超えて、潜在的にエミュレートされた圧縮機の理論を支持するものである。
  論文  参考訳（メタデータ） (2021-10-07T09:38:15Z)
• From Information Theory Puzzles in Deletion Channels to Deniability in Quantum Cryptography [0.0]
  まず、実験データに基づいて、後部のエントロピーが定数列によって最小化されることを予想する。 次に,DC-QKEを提案するために,隠蔽通信とデニビリティの接続を確立する。 完全ホモモルフィック暗号をベースとした,効率的な耐保磁・量子セキュリティ投票方式を提案する。
  論文  参考訳（メタデータ） (2020-03-25T22:20:47Z)

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

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