論文の概要: Cut query algorithms with star contraction
- arxiv url: http://arxiv.org/abs/2201.05674v1
- Date: Fri, 14 Jan 2022 21:13:49 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-01 04:23:37.676852
- Title: Cut query algorithms with star contraction
- Title（参考訳）: 恒星収縮による問合せアルゴリズムの切断
- Authors: Simon Apers, Yuval Efron, Pawe{\l} Gawrychowski, Troy Lee, Sagnik
Mukhopadhyay, Danupon Nanongkai
- Abstract要約: カットクエリを用いた単純なグラフのエッジ接続を決定する複雑さについて検討する。
エッジ接続を$O(n)$ cutクエリで計算する有界誤りランダム化アルゴリズムが存在することを示す。
また、$O(sqrtn)$ cutクエリでエッジ接続を計算する有界エラー量子アルゴリズムがあることも示している。
- 参考スコア（独自算出の注目度）: 4.570617424761779
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the complexity of determining the edge connectivity of a simple
graph with cut queries. We show that (i) there is a bounded-error randomized
algorithm that computes edge connectivity with $O(n)$ cut queries, and (ii)
there is a bounded-error quantum algorithm that computes edge connectivity with
$\~O(\sqrt{n})$ cut queries. We prove these results using a new technique
called "star contraction" to randomly contract edges of a graph while
preserving non-trivial minimum cuts. In star contraction vertices randomly
contract an edge incident on a small set of randomly chosen vertices. In
contrast to the related 2-out contraction technique of Ghaffari, Nowicki, and
Thorup [SODA'20], star contraction only contracts vertex-disjoint star
subgraphs, which allows it to be efficiently implemented via cut queries.
The $O(n)$ bound from item (i) was not known even for the simpler problem of
connectivity, and improves the $O(n\log^3 n)$ bound by Rubinstein, Schramm, and
Weinberg [ITCS'18]. The bound is tight under the reasonable conjecture that the
randomized communication complexity of connectivity is $\Omega(n\log n)$, an
open question since the seminal work of Babai, Frankl, and Simon [FOCS'86]. The
bound also excludes using edge connectivity on simple graphs to prove a
superlinear randomized query lower bound for minimizing a symmetric submodular
function. Item (ii) gives a nearly-quadratic separation with the randomized
complexity and addresses an open question of Lee, Santha, and Zhang [SODA'21].
The algorithm can also be viewed as making $\~O(\sqrt{n})$ matrix-vector
multiplication queries to the adjacency matrix.
Finally, we demonstrate the use of star contraction outside of the cut query
setting by designing a one-pass semi-streaming algorithm for computing edge
connectivity in the vertex arrival setting. This contrasts with the edge
arrival setting where two passes are required.
- Abstract（参考訳）: カットクエリを用いた単純なグラフのエッジ接続を決定する複雑さについて検討する。
私たちはそれを示します
(i)$O(n)$ cutクエリでエッジ接続を計算する有界エラーランダム化アルゴリズムがあり、
(ii)$\~O(\sqrt{n})$ cutクエリでエッジ接続を計算する有界エラー量子アルゴリズムがある。
これらの結果は、非自明な最小カットを保ちながら、グラフのエッジをランダムに収縮させる「星収縮」と呼ばれる新しい手法を用いて証明する。
恒星収縮頂点では、ランダムに選択された頂点の小さなセットでエッジインシデントをランダムに収縮する。
Ghaffari, Nowicki, Thorup [SODA'20] の関連する2段階の縮約技術とは対照的に、星の縮約は頂点不整合星サブグラフのみを縮約し、カットクエリによって効率よく実装できる。
アイテムから縛られた$o(n)$
i) は接続性の単純な問題でさえも知られておらず、Rubinstein, Schramm, Weinberg [ITCS'18] による$O(n\log^3 n)$バウンドを改善する。
この境界は、接続のランダム化通信の複雑さが$\omega(n\log n)$であるという合理的な予想のもとに厳密であり、これはbabai, frankl, simon [focs'86] の独創的な研究以来のオープン問題である。
境界はまた、対称部分モジュラー関数を最小化するために超線形ランダム化クエリ下限を証明するために単純なグラフ上のエッジ接続を使用することも除外する。
項目
(ii) ランダム化複雑性とほぼ二乗分離を与え、Lee, Santha, Zhang [SODA'21] のオープンな疑問に対処する。
このアルゴリズムは、随伴行列に対して$\~o(\sqrt{n})$ matrix-vector乗算クエリを作ることもできる。
最後に,頂点到達設定におけるエッジ接続性を計算するための1パスセミストリーミングアルゴリズムを設計することにより,カットクエリ設定の外部でのスター収縮の利用を実証する。
これは、2つのパスが必要なエッジ到着設定とは対照的である。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Finding the KT partition of a weighted graph in near-linear time [1.572727650614088]
カワラバヤシとソープは、単純なグラフ $G = (V,E)$ の最小カットに対して、ほぼ自明な時間決定論的アルゴリズムを与えた。
重み付きグラフの$(1+varepsilon)$-KTパーティションを見つけるために、線形に近い時間ランダム化アルゴリズムを与える。
論文 参考訳（メタデータ） (2021-11-02T05:26:10Z) - A sublinear query quantum algorithm for s-t minimum cut on dense simple
graphs [1.0435741631709405]
グラフにおける$soperatorname-t$最小カットは、削除が$s$と$t$を切断するエッジの最小ウェイトサブセットに対応する。
この研究では、無向グラフ上の最小$soperatorname-t$カット問題に対する量子アルゴリズムを記述する。
論文 参考訳（メタデータ） (2021-10-29T07:35:46Z) - Sublinear Time and Space Algorithms for Correlation Clustering via
Sparse-Dense Decompositions [9.29659220237395]
本稿では,相関クラスタリングの解法を提案する。
我々は高効率な時間と空間の複雑さを持つサブ線形アルゴリズムを得る。
提案手法の主な要素はスパース線グラフ分解への新規な接続である。
論文 参考訳（メタデータ） (2021-09-29T16:25:02Z) - Quantum complexity of minimum cut [0.2538209532048867]
隣接行列モデルにおける最小カット問題の量子クエリと時間複雑性を特徴付ける。
我々のアルゴリズムは、Apers and de Wolf (FOCS 2020) によるグラフスカラー化のための量子アルゴリズムを用いており、Kawarabayashi and Thorup (STOC 2015) と Rubinstein, Schramm and Weinberg (ITCS 2018) による準最小カットの構造に関する結果である。
論文 参考訳（メタデータ） (2020-11-19T13:51:49Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Quantum Distributed Complexity of Set Disjointness on a Line [3.2590610391507444]
Set Disjointness on a Line は分散コンピューティングシナリオにおける Set Disjointness 問題の変種である。
条件のない$widetildeOmegabig(sqrt[3]n d2+sqrtn, big)$$$$d + 1$プロセッサを持つライン上の集合不整合のラウンドを証明する。
論文 参考訳（メタデータ） (2020-02-26T21:17:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。