論文の概要: On the query complexity of connectivity with global queries
- arxiv url: http://arxiv.org/abs/2109.02115v1
- Date: Sun, 5 Sep 2021 16:22:55 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-16 02:52:16.299820
- Title: On the query complexity of connectivity with global queries
- Title（参考訳）: グローバルクエリとの接続のクエリ複雑性について
- Authors: Arinta Auza and Troy Lee
- Abstract要約: グラフがグローバルクエリと結びついているかどうかを判断する際のクエリの複雑さについて検討する。
ゼロエラーランダム化アルゴリズムは接続性を解決するために,$Omega(n)$リニアクエリを生成する必要がある。
- 参考スコア（独自算出の注目度）: 0.2538209532048867
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the query complexity of determining if a graph is connected with
global queries. The first model we look at is matrix-vector multiplication
queries to the adjacency matrix. Here, for an $n$-vertex graph with adjacency
matrix $A$, one can query a vector $x \in \{0,1\}^n$ and receive the answer
$Ax$. We give a randomized algorithm that can output a spanning forest of a
weighted graph with constant probability after $O(\log^4(n))$ matrix-vector
multiplication queries to the adjacency matrix. This complements a result of
Sun et al.\ (ICALP 2019) that gives a randomized algorithm that can output a
spanning forest of a graph after $O(\log^4(n))$ matrix-vector multiplication
queries to the signed vertex-edge incidence matrix of the graph. As an
application, we show that a quantum algorithm can output a spanning forest of
an unweighted graph after $O(\log^5(n))$ cut queries, improving and simplifying
a result of Lee, Santha, and Zhang (SODA 2021), which gave the bound
$O(\log^8(n))$.
In the second part of the paper, we turn to showing lower bounds on the
linear query complexity of determining if a graph is connected. If $w$ is the
weight vector of a graph (viewed as an $\binom{n}{2}$ dimensional vector), in a
linear query one can query any vector $z \in \mathbb{R}^{n \choose 2}$ and
receive the answer $\langle z, w\rangle$. We show that a zero-error randomized
algorithm must make $\Omega(n)$ linear queries in expectation to solve
connectivity. As far as we are aware, this is the first lower bound of any kind
on the unrestricted linear query complexity of connectivity. We show this lower
bound by looking at the linear query \emph{certificate complexity} of
connectivity, and characterize this certificate complexity in a linear
algebraic fashion.
- Abstract（参考訳）: グラフがグローバルクエリと接続されているかどうかを判断するクエリの複雑さについて検討する。
最初に見るモデルは、隣接行列に対する行列-ベクトル乗法クエリです。
ここで、隣接行列 $a$ を持つ$n$-vertex グラフに対して、ベクトル $x \in \{0,1\}^n$ をクエリし、答え $ax$ を受け取ることができる。
重み付きグラフのスパンディングフォレストを一定の確率で出力できるランダム化アルゴリズムを,随伴行列に対する$o(\log^4(n))$ matrix-vector乗算クエリの後に与える。
これはsunとalの結果を補完する。
O(\log^4(n))$Matrix-vector乗算クエリの後にグラフのスパンニングフォレストをグラフの符号付き頂点入射行列に出力できるランダム化アルゴリズム(ICALP 2019)を提供する。
応用として、量子アルゴリズムは、$O(\log^5(n))$カットクエリの後に非重み付きグラフのスパンニングフォレストを出力し、Lee, Santha, Zhang(SODA 2021)の結果を改善し、単純化することで、有界な$O(\log^8(n))$を与える。
論文の第2部では、グラフが接続されているかどうかを決定する線形クエリの複雑さについて、より低い境界を示す。
もし$w$ がグラフの重みベクトル ($\binom{n}{2}$ dimensional vector) であるなら、線型クエリでは任意のベクトル $z \in \mathbb{r}^{n \choose 2}$ をクエリし、答え $\langle z, w\rangle$ を受け取ることができる。
ゼロエラーランダム化アルゴリズムは接続性を解決するために$\Omega(n)$リニアクエリを生成する必要がある。
我々が知る限り、これは接続の制限のない線形クエリの複雑さにおいて、あらゆる種類の最初の下限である。
我々は、接続の線形クエリ \emph{certificate complexity} を見てこの下限を示し、この証明複雑性を線形代数的方法で特徴づける。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - Fast Computation of Generalized Eigenvectors for Manifold Graph
Embedding [38.902986549367434]
我々は、高速実行に既存の高速極端固有ベクトル計算アルゴリズムを利用する。
我々の埋め込みは文献の中では最速であり、多様体グラフのクラスタリング性能は最高のものとなっている。
論文 参考訳（メタデータ） (2021-12-15T03:45:39Z) - 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) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳（メタデータ） (2021-05-17T16:40:48Z) - Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative
GLASSO and Projection [58.5350491065936]
グラフ Laplacian 行列 $L$ 上の構造的仮定を考える。
最初の$K$ eigenvectors of $L$は、例えばドメイン固有の基準に基づいて事前選択される。
本稿では,H_u+$$$$barC$で最も適切なグラフラプラシアン行列$L*を計算するために,効率的なハイブリッドグラフラッソ/投影アルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-10-25T18:12:50Z) - 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) - Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and
Graph Problems [58.83118651518438]
ベクトル行列ベクトルクエリを用いて行列について学習する一般的な問題を考える。
これらのクエリは、固定フィールド上の$boldsymbolumathrmTboldsymbolMboldsymbolv$の値を提供する。
我々は、線形代数、統計、グラフにまたがる様々な問題に対して、新しい上界と下界を提供する。
論文 参考訳（メタデータ） (2020-06-24T19:33:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。