論文の概要: On the communication complexity of finding a king in a tournament
- arxiv url: http://arxiv.org/abs/2402.14751v1
- Date: Thu, 22 Feb 2024 18:11:19 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-23 14:15:08.903364
- Title: On the communication complexity of finding a king in a tournament
- Title(参考訳): トーナメントにおけるキング発見のコミュニケーション複雑性について
- Authors: Nikhil S. Mande, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh
- Abstract要約: エッジが2つのプレイヤー間で分割されるタスクの通信複雑性について検討する。
トーナメントのソースを見つけることは、無向グラフ上のよく研究されているClique vs. Independent Set(CIS)問題と同等であることを示す。
- 参考スコア(独自算出の注目度): 0.5999777817331317
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A tournament is a complete directed graph. A king in a tournament is a vertex
v such that every other vertex is reachable from v via a path of length at most
2. It is well known that every tournament has at least one king, one of which
is a maximum out-degree vertex. The tasks of finding a king, a maximum
out-degree vertex and a source in a tournament has been relatively well studied
in the context of query complexity. We study the communication complexity of
these tasks, where the edges are partitioned between two players. The following
are our main results for n-vertex tournaments:
1) The deterministic communication complexity of finding whether a source
exists is tilde{Theta}(log^2 n).
2) The deterministic and randomized communication complexities of finding a
king are Theta(n). The quantum communication complexity is
tilde{Theta}(sqrt{n}).
3) The deterministic, randomized and quantum communication complexities of
finding a maximum out-degree vertex are Theta(n log n), tilde{Theta}(n) and
tilde{Theta}(sqrt{n}), respectively.
Our upper bounds hold for all partitions of edges, and the lower bounds for a
specific partition of the edges. To show the first bullet above, we show,
perhaps surprisingly, that finding a source in a tournament is equivalent to
the well-studied Clique vs. Independent Set (CIS) problem on undirected graphs.
Our bounds for finding a source then follow from known bounds on the complexity
of the CIS problem. In view of this equivalence, we can view the task of
finding a king in a tournament to be a natural generalization of CIS.
One of our lower bounds uses a fooling-set based argument, and all our other
lower bounds follow from carefully-constructed reductions from
Set-Disjointness.
- Abstract(参考訳): トーナメントは完全な有向グラフである。
トーナメントの王は頂点 v であり、他の頂点はすべて、最大 2 の経路で v から到達可能である。
各トーナメントには少なくとも1つの王がおり、そのうちの1つは最大外度頂点である。
キング、最大外度頂点、トーナメントのソースを見つけるタスクは、クエリの複雑さの文脈で比較的よく研究されている。
これらのタスクの通信複雑性について検討し、エッジを2つのプレイヤー間で分割する。
1) ソースが存在するかどうかを判断する決定論的コミュニケーションの複雑さは tilde{theta}(log^2 n) である。
2) キングを見つけるための決定論的およびランダムな通信複雑性は、Theta(n) である。
量子通信の複雑さはtilde{theta}(sqrt{n})である。
3) 最大外度頂点を求める決定論的、ランダム化、および量子通信の複雑さは、それぞれ Theta(n log n) と tilde{Theta}(n) と tilde{Theta}(sqrt{n}) である。
私たちの上界は、エッジのすべてのパーティションと、エッジの特定のパーティションの下界を保持する。
上の最初の弾丸を示すために、おそらく驚くことに、トーナメントでソースを見つけることは、無向グラフ上のよく研究されたclique vs. independent set(cis)問題と同等である。
情報源を見つけるための我々の限界は、CIS問題の複雑さに関する既知の境界から従う。
この等価性の観点から、トーナメントにおける王の発見は、CISの自然な一般化であると考えることができる。
我々の下限の1つは、愚かな集合に基づく引数を使い、他の下限の全ては、慎重に構成されたSet-Disjointnessからの還元から従う。
関連論文リスト
- Randomized and quantum query complexities of finding a king in a
tournament [0.0]
決定論的クエリの複雑さについて、最もよく知られた上限と下限を示す。
我々の貢献は、*randomized* および *quantum* クエリモデルにおける Theta(n) および Theta(sqrtn) の*tight* 境界(対数要素まで)を示すことである。
論文 参考訳(メタデータ) (2023-08-04T17:21:11Z) - Global Nash Equilibrium in Non-convex Multi-player Game: Theory and
Algorithms [66.8634598612777]
ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。
また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
論文 参考訳(メタデータ) (2023-01-19T11:36:50Z) - Discrete Bulk Reconstruction [4.467248776406005]
ブラックホールの内部などの領域を再構築したい場合,AdS/CFTは指数関数的に複雑であることを示す。
また,複数の1次元境界がワームホールを介して接続される場合にも,初期進行が見られた。
論文 参考訳(メタデータ) (2022-10-27T16:39:29Z) - Connes implies Tsirelson: a simple proof [91.3755431537592]
コンヌ埋め込み問題は同期的ツィレルソン予想を意味することを示す。
また、コンネスの代数 $mathcalRomega$ の異なる構成もコンネス埋め込み問題に現れる。
論文 参考訳(メタデータ) (2022-09-16T13:59:42Z) - Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。
これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
論文 参考訳(メタデータ) (2022-02-03T18:18:28Z) - Cut query algorithms with star contraction [4.570617424761779]
カットクエリを用いた単純なグラフのエッジ接続を決定する複雑さについて検討する。
エッジ接続を$O(n)$ cutクエリで計算する有界誤りランダム化アルゴリズムが存在することを示す。
また、$O(sqrtn)$ cutクエリでエッジ接続を計算する有界エラー量子アルゴリズムがあることも示している。
論文 参考訳(メタデータ) (2022-01-14T21:13:49Z) - A Theory of Tournament Representations [4.969254618158096]
我々はパラメトリックトーナメント表現を理解するための新しい理論を開発した。
私たちの最初の貢献は、$d$次元表現から生じるトーナメントのクラスを構造的に特徴づけることです。
さらに2ドルのトーナメントは、関連する禁止されたフリップクラスがわずか2ドルのトーナメントを含むことを示すことで、完全にランク付けします。
論文 参考訳(メタデータ) (2021-10-06T09:08:00Z) - Almost Optimal Algorithms for Two-player Markov Games with Linear
Function Approximation [92.99933928528797]
同時動作による2プレイヤーゼロサムマルコフゲームの強化学習について検討した。
我々は,「不確かさの最適性」に基づくアルゴリズムナッシュ-UCRL-VTRを提案する。
我々は、Nash-UCRL-VTR が $tildeO(dHsqrtT)$ regret を確実に達成できることを示し、$d$ は線型関数次元である。
論文 参考訳(メタデータ) (2021-02-15T09:09:16Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-20T04:29:18Z) - Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。
本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-22T05:00:13Z) - Query Complexity of Tournament Solutions [12.192470787877594]
我々は、コペランド集合、スレーター集合、マルコフ集合、バイパルチザン集合、未発見集合、バンクス集合、および最上位サイクルを見つけるアルゴリズムが、最悪の場合、$Omega(n2)$ edgesを問う必要があることを示す。
肯定的な面では、入力トーナメントの上位サイクルのサイズが最大で1kドルであれば、上記のすべてのトーナメントソリューションが見つかることを証明して、クエリの複雑さを低く抑えることができる。
論文 参考訳(メタデータ) (2016-11-18T18:19:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。