論文の概要: Lower Bounds for Leader Election and Collective Coin Flipping, Revisited

• arxiv url: http://arxiv.org/abs/2504.01856v1
• Date: Wed, 02 Apr 2025 16:08:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-03 13:17:34.113356
• Title: Lower Bounds for Leader Election and Collective Coin Flipping, Revisited
• Title（参考訳）: 英大統領選と連立与党の連立与党・連立与党・連立与党・与党・与党・与党・与党・与党・与党・与党・与党・与党・与党・与党・与党・与党・与党・
• Authors: Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, Rocco Servedio,
• Abstract要約: 我々は、$k$ラウンドのコインフリッププロトコルは、$O(ell/log(k)(ell))$ bad playerによってバイアスを受けることができることを示した。 また、ラウンド毎にマルチビットメッセージを許容するプロトコルの下位境界も導出します。
• 参考スコア（独自算出の注目度）: 0.47998222538650526
• License:
• Abstract: We study the tasks of collective coin flipping and leader election in the full-information model. We prove new lower bounds for coin flipping protocols, implying lower bounds for leader election protocols. We show that any $k$-round coin flipping protocol, where each of $\ell$ players sends 1 bit per round, can be biased by $O(\ell/\log^{(k)}(\ell))$ bad players. For all $k>1$ this strengthens previous lower bounds [RSZ, SICOMP 2002], which ruled out protocols resilient to adversaries controlling $O(\ell/\log^{(2k-1)}(\ell))$ players. Consequently, we establish that any protocol tolerating a linear fraction of corrupt players, with only 1 bit per round, must run for at least $\log^*\ell-O(1)$ rounds, improving on the prior best lower bound of $\frac12 \log^*\ell-\log^*\log^*\ell$. This lower bound matches the number of rounds, $\log^*\ell$, taken by the current best coin flipping protocols from [RZ, JCSS 2001], [F, FOCS 1999] that can handle a linear sized coalition of bad players, but with players sending unlimited bits per round. We also derive lower bounds for protocols allowing multi-bit messages per round. Our results show that the protocols from [RZ, JCSS 2001], [F, FOCS 1999] that handle a linear number of corrupt players are almost optimal in terms of round complexity and communication per player in a round. A key technical ingredient in proving our lower bounds is a new result regarding biasing most functions from a family of functions using a common set of bad players and a small specialized set of bad players specific to each function that is biased. We give improved constant-round coin flipping protocols in the setting that each player can send 1 bit per round. For two rounds, our protocol can handle $O(\ell/(\log\ell)(\log\log\ell)^2)$ sized coalition of bad players; better than the best one-round protocol by [AL, Combinatorica 1993] in this setting.
• Abstract（参考訳）: 本研究は,全情報モデルにおけるコインフリップとリーダー選挙の課題について考察する。 我々は、コインフリッププロトコルの新たな下位境界を証明し、リーダー選挙プロトコルの下位境界を示唆する。 1ラウンドあたり1ビットの$\ell$プレーヤーが送信される$k$ラウンドのコインフリッププロトコルは、$O(\ell/\log^{(k)}(\ell))$ bad playerによってバイアスを受けることができる。 すべての$k>1$に対して、これは以前の下界(RSZ, SICOMP 2002)を強化し、$O(\ell/\log^{(2k-1)}(\ell))$プレーヤーを制御する敵に耐性のあるプロトコルを除外する。 その結果、少なくとも$\log^*\ell-O(1)$のラウンドは1ラウンドあたり1ビットしか持たない、腐敗したプレイヤーの線形分数に許容するプロトコルが少なくとも$\log^*\ell-O(1)$のラウンドで実行されなければならず、以前の$\frac12 \log^*\ell-\log^*\ell-\log^*\ell$よりも低い範囲で改善される。 この下限はラウンド数と一致する。$\log^*\ell$は]RZ, JCSS 2001], [F, FOCS 1999] の現在の最高のコインフリッププロトコルによって取られ、悪いプレイヤーの線形サイズの連立を処理できるが、ラウンドごとに無制限のビットを送信できる。 また、ラウンド毎にマルチビットメッセージを許容するプロトコルの下位境界も導出します。 以上の結果から, [RZ, JCSS 2001], [F, FOCS 1999] の線形プレイヤー数を扱うプロトコルは, ラウンド中のプレイヤーごとのラウンド複雑性と通信の点でほぼ最適であることが示唆された。 下限を証明するための重要な技術的要素は、共通の悪いプレイヤーのセットと、バイアスを受けている各関数に特有の小さな特別な悪いプレイヤーのセットを使用して、関数のファミリーからほとんどの関数をバイアスする、という新しい結果である。 我々は、各プレイヤーが1ラウンドあたり1ビットを送信できるように、改良されたコンスタントラウンドコインフリッププロトコルを提供する。 2ラウンドで、弊社のプロトコルは、$O(\ell/(\log\ell)(\log\log\ell)^2)$の悪者の連合を扱える。

関連論文リスト

• Best of Both Worlds: Regret Minimization versus Minimax Play [57.68976579579758]
  この結果から,悪用可能な相手からOmega(T)$を得ることができながら,少なくともO(1)$損失のリスクを保証できることが分かる。
  論文  参考訳（メタデータ） (2025-02-17T11:04:01Z)
• Corrupted Learning Dynamics in Games [62.73758165845971]
  すべてのプレイヤーが楽観的な追従型リーダー(OFTRL)に従うと、平衡は$O(log T)$の速さで計算できる。 本稿では,各プレイヤーが所定のアルゴリズムによって提案される戦略から逸脱する程度に依存する速度で,適応的に平衡を求める学習ダイナミクスを提案する。
  論文  参考訳（メタデータ） (2024-12-10T02:23:44Z)
• Asynchronous Approximate Agreement with Quadratic Communication [23.27199615640474]
  非同期ネットワークは$n$のメッセージ送信パーティで、そのうちの最大$t$はビザンチンです。 本研究では,入力の凸内積にほぼ等しい出力が得られるような近似一致について検討する。 これは、信頼できるブロードキャスト毎に$Theta(n2)$メッセージ、またはイテレーション毎に$Theta(n3)$メッセージを取る。
  論文  参考訳（メタデータ） (2024-08-10T09:03:06Z)
• 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)
• Context-lumpable stochastic bandits [49.024050919419366]
  我々は、$S$コンテキストと$K$アクションによる文脈的盗賊問題を考える。 我々は,最大$widetilde O(r (S +K )/epsilon2)$サンプルを用いて,$epsilon$-optimal Policyを出力するアルゴリズムを提案する。 後悔の設定では、T$までの累積後悔を$widetilde O(sqrtr3(S+K)T)$で束縛するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2023-06-22T17:20:30Z)
• Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error [1.6522364074260811]
  誤差が小さいEquality関数のランダム化および量子化通信複雑性を$epsilon$で調べる。 任意の$log(n/epsilon)-log(sqrtn/epsilon)+3$プロトコルが少なくとも$log(n/epsilon)-log(sqrtn/epsilon)-O(1)$ qubitsを通信することを示す。
  論文  参考訳（メタデータ） (2021-07-25T13:52:42Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。 目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
  論文  参考訳（メタデータ） (2020-09-21T04:13:34Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip [2.469280630208887]
  コインフリッピングプロトコルでは、計算上の敵は、プロトコルの実行に沿ってどのパーティを腐敗させるかを選択することができる。 我々は、(丸い複雑さの)$n$-partyプロトコルが$omega(sqrtn)$ corruptionsに回復可能であることを証明している。
  論文  参考訳（メタデータ） (2020-05-04T15:29:11Z)

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

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