論文の概要: Learning Graph Partitions

• arxiv url: http://arxiv.org/abs/2112.07897v1
• Date: Wed, 15 Dec 2021 05:28:45 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-17 00:24:15.388764
• Title: Learning Graph Partitions
• Title（参考訳）: グラフ分割の学習
• Authors: Sayan Mukherjee
• Abstract要約: グラフの連結成分への分割が与えられたとき、会員オラクルはグラフの任意の2つの頂点が同じ成分に含まれるか否かを主張する。 我々は$nge kge 2$の場合、$k$コンポーネントで$n$-vertex隠れグラフのコンポーネントを学ぶには、少なくとも$frac12(n-k)(k-1)$メンバシップクエリが必要であることを証明している。
• 参考スコア（独自算出の注目度）: 2.3224617218247126
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Given a partition of a graph into connected components, the membership oracle asserts whether any two vertices of the graph lie in the same component or not. We prove that for $n\ge k\ge 2$, learning the components of an $n$-vertex hidden graph with $k$ components requires at least $\frac{1}{2}(n-k)(k-1)$ membership queries. This proves the optimality of the $O(nk)$ algorithm proposed by Reyzin and Srivastava (2007) for this problem, improving on the best known information-theoretic bound of $\Omega(n\log k)$ queries. Further, we construct an oracle that can learn the number of components of $G$ in asymptotically fewer queries than learning the full partition, thus answering another question posed by the same authors. Lastly, we introduce a more applicable version of this oracle, and prove asymptotically tight bounds of $\widetilde\Theta(m)$ queries for both learning and verifying an $m$-edge hidden graph $G$ using this oracle.
• Abstract（参考訳）: 連結されたコンポーネントにグラフを分割すると、oracleはグラフの任意の2つの頂点が同じコンポーネントにあるかどうかを断言する。 我々は$n\ge k\ge 2$に対して、$k$コンポーネントを持つ$n$-vertex隠れグラフのコンポーネントを学ぶには、少なくとも$\frac{1}{2}(n-k)(k-1)$メンバシップクエリが必要であることを証明している。 これは、Reyzin と Srivastava (2007) がこの問題に対して提案した$O(nk)$アルゴリズムの最適性を証明し、$Omega(n\log k)$クエリの最もよく知られた情報理論境界を改善する。 さらに,本研究では,完全分割を学習するよりも漸近的に少ないクエリで$G$の成分数を学習できるオラクルを構築し,同じ著者による別の質問に答える。 最後に、このオラクルのより適用可能なバージョンを紹介し、このオラクルを使って$m$のエッジ隠れグラフを学習および検証するための$\widetilde\Theta(m)$クエリの漸近的に厳密な境界を証明します。

関連論文リスト

• Learning-augmented Maximum Independent Set [20.58740333788296]
  学習強化アルゴリズムの枠組みにおける一般グラフ上での最大独立集合(MIS)問題について検討する。 機械学習モデルから得られた予測によって得られたオラクルの存在下で、この障壁を破ることができることを示す。
  論文  参考訳（メタデータ） (2024-07-16T04:05:40Z)
• A quantum algorithm for learning a graph of bounded degree [1.8130068086063336]
  本稿では,最大$tildeO(d2m3/4)$量子クエリにおいて,$G$のエッジを学習するアルゴリズムを提案する。 特に、確率の高い確率で$tildeO(sqrtm)$量子クエリでサイクルとマッチングを学習するランダム化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-28T21:23:40Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Simplified Quantum Algorithm for the Oracle Identification Problem [0.0]
  oracleは未知の文字列のビットに$x$ of length$n$をアクセスし、既知のセットである$Csubseteq0,1n$に属することを約束する。 目標は、できるだけ少数のオラクルへのクエリを使って$x$を識別することだ。 この問題に対して,クエリ複雑性を$Oleft(sqrtfracnlog M log(n/log M)+1right)$,$M$は$C$である。
  論文  参考訳（メタデータ） (2021-09-08T19:48:27Z)
• Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
  本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。 我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-06-09T05:39:05Z)
• 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)
• Quantum algorithms for graph problems with cut queries [17.149741568581096]
  量子アルゴリズムは、$O(d log(n)2) の後に最大$d$のグラフを学習できることを示す。 また、量子アルゴリズムは、$O(sqrtm log(n)3/2)$多くのカットクエリで一般的なグラフを学習できることを示す。
  論文  参考訳（メタデータ） (2020-07-16T12:21:01Z)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)
• Query complexity of heavy hitter estimation [6.373263986460191]
  我々は、サブセット $mathcalSgamma_mathcalP$ を、基礎となる分布 $mathcalP$ をサポートする要素の特定の問題を考える。 それぞれのクエリはインデックス$i$であり、オラクルは値を$X_i$と$(b)$はペア$(i,j)$である。 それぞれの問合せモデルに対して、各ラウンドでどの問合せを全体に依存するかを決定するシーケンシャルな推定アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-05-29T07:15:46Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。 このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
  論文  参考訳（メタデータ） (2020-02-17T10:53:50Z)

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

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