論文の概要: Randomized and quantum query complexities of finding a king in a
tournament
- arxiv url: http://arxiv.org/abs/2308.02472v1
- Date: Fri, 4 Aug 2023 17:21:11 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-07 12:04:29.978140
- Title: Randomized and quantum query complexities of finding a king in a
tournament
- Title（参考訳）: トーナメントでキングを見つけることのランダム化と量子クエリの複雑さ
- Authors: Nikhil S. Mande, Manaswi Paraashar and Nitin Saurabh
- Abstract要約: 決定論的クエリの複雑さについて、最もよく知られた上限と下限を示す。
我々の貢献は、*randomized* および *quantum* クエリモデルにおける Theta(n) および Theta(sqrtn) の*tight* 境界(対数要素まで)を示すことである。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A tournament is a complete directed graph. It is well known that every
tournament contains at least one vertex v such that every other vertex is
reachable from v by a path of length at most 2. All such vertices v are called
*kings* of the underlying tournament. Despite active recent research in the
area, the best-known upper and lower bounds on the deterministic query
complexity (with query access to directions of edges) of finding a king in a
tournament on n vertices are from over 20 years ago, and the bounds do not
match: the best-known lower bound is Omega(n^{4/3}) and the best-known upper
bound is O(n^{3/2}) [Shen, Sheng, Wu, SICOMP'03]. Our contribution is to show
essentially *tight* bounds (up to logarithmic factors) of Theta(n) and
Theta(sqrt{n}) in the *randomized* and *quantum* query models, respectively. We
also study the randomized and quantum query complexities of finding a maximum
out-degree vertex in a tournament.
- Abstract（参考訳）: トーナメントは完全な有向グラフである。
すべてのトーナメントが少なくとも1つの頂点 v を含み、すべての頂点が v から到達可能な長さ 2 の経路で到達可能であることはよく知られている。
これらすべての頂点 v は、下層のトーナメントの *kings* と呼ばれる。
この分野における最近の活発な研究にもかかわらず、n頂点でのトーナメントでキングを見つける決定論的クエリの複雑さ(エッジの方向へのクエリアクセスを含む)の最もよく知られた上限は20年以上前であり、その境界は一致しない:最もよく知られた下限はomega(n^{4/3})であり、最もよく知られた上限はo(n^{3/2})である。
我々の貢献は、基本的に、*randomized* と *quantum* のクエリモデルにおける Theta(n) と Theta(sqrt{n}) の*tight* 境界を示すことである。
また,トーナメントにおける最大外角頂点の探索におけるランダム化と量子クエリの複雑さについても検討した。
関連論文リスト
- On the communication complexity of finding a king in a tournament [0.5999777817331317]
エッジが2つのプレイヤー間で分割されるタスクの通信複雑性について検討する。
トーナメントのソースを見つけることは、無向グラフ上のよく研究されているClique vs. Independent Set(CIS)問題と同等であることを示す。
論文 参考訳（メタデータ） (2024-02-22T18:11:19Z) - A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points [50.90125395570797]
このことは対数的因子の中でのciteSaundersonCPW12 の予想をほぼ成立させる。
後者の予想は、機械学習とある種の統計上の問題に対する2乗下界との結びつきから、過去10年間で大きな注目を集めている。
論文 参考訳（メタデータ） (2022-12-21T17:48:01Z) - Lackadaisical quantum walk in the hypercube to search for multiple
marked vertices [0.0]
本稿では,自己ループを用いたハイパーキューブにおける量子ウォーキングに関するいくつかの問題を実験的に解決する。
隣人がマークされている場合、成功の確率は1ドル近くになる。
論文 参考訳（メタデータ） (2021-08-20T23:19:55Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - Lower Bounds and Accelerated Algorithms for Bilevel Optimization [62.192297758346484]
バイレベル最適化は、最近の機械学習問題に広く応用されているため、近年、関心が高まりつつある。
結果がminimaxアプリケーションよりも難しいことを示します。
論文 参考訳（メタデータ） (2021-02-07T21:46:29Z) - Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit
Feedback [51.21673420940346]
コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。
我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。
有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
論文 参考訳（メタデータ） (2021-01-21T10:35:09Z) - 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) - Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
スパースな ErdHos-R'enyi ランダムグラフにおいて,大きな独立集合を求めるアルゴリズム的タスクについて検討する。
低次アルゴリズムのクラスは、半最適サイズの独立した集合を見つけることができるが、それ以上は見つからないことを示す。
論文 参考訳（メタデータ） (2020-10-13T17:26:09Z) - Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk [0.0]
量子ウォーク(quantum walk)は、グラフ上の離散時間(離散時間)の量子ウォークである。
完全グラフ、離散トーラス、サイクル、正規完全二部グラフの空間探索を改善することができる。
この仮説を支持する数値シミュレーションをいくつか提示する。
論文 参考訳（メタデータ） (2020-02-26T00:10:38Z) - Improved Approximate Degree Bounds For k-distinctness [2.1845023178514413]
開問題は、サイズ N の入力上の k-判別関数の量子複雑性を解くことである。
任意の定数 k >= 4 に対して、Omega(N(3/4)-1/(4k)) への下界を改善する。
これは、例えば、4-連続性はより難しいという最初の証明をもたらす。
論文 参考訳（メタデータ） (2020-02-19T19:04:44Z) - Query Complexity of Tournament Solutions [12.192470787877594]
我々は、コペランド集合、スレーター集合、マルコフ集合、バイパルチザン集合、未発見集合、バンクス集合、および最上位サイクルを見つけるアルゴリズムが、最悪の場合、$Omega(n2)$ edgesを問う必要があることを示す。
肯定的な面では、入力トーナメントの上位サイクルのサイズが最大で1kドルであれば、上記のすべてのトーナメントソリューションが見つかることを証明して、クエリの複雑さを低く抑えることができる。
論文 参考訳（メタデータ） (2016-11-18T18:19:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。