論文の概要: Quantum Distributed Complexity of Set Disjointness on a Line
- arxiv url: http://arxiv.org/abs/2002.11795v5
- Date: Tue, 8 Mar 2022 22:07:19 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-01 20:55:27.950839
- Title: Quantum Distributed Complexity of Set Disjointness on a Line
- Title（参考訳）: 直線上の集合不連続性の量子分散複素性
- Authors: Frederic Magniez and Ashwin Nayak
- Abstract要約: Set Disjointness on a Line は分散コンピューティングシナリオにおける Set Disjointness 問題の変種である。
条件のない$widetildeOmegabig(sqrt[3]n d2+sqrtn, big)$$$$d + 1$プロセッサを持つライン上の集合不整合のラウンドを証明する。
- 参考スコア（独自算出の注目度）: 3.2590610391507444
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Set Disjointness on a Line is a variant of the Set Disjointness problem in a
distributed computing scenario with $d+1$ processors arranged on a path of
length $d$. It was introduced by Le Gall and Magniez (PODC 2018) for proving
lower bounds on the quantum distributed complexity of computing the diameter of
an arbitrary network in the CONGEST model. However, they were only able to
provide a lower bound when the local memory used by the processors on the
intermediate vertices of the path consists of O$( \log n)$ qubits for $n$-bit
inputs. We prove an unconditional lower bound of
$\widetilde{\Omega}\big(\sqrt[3]{n d^2}+\sqrt{n} \, \big)$ rounds for Set
Disjointness on a Line with $d + 1$ processors. The result gives us a new lower
bound of $\widetilde{\Omega} \big( \sqrt[3]{n\delta^2}+\sqrt{n} \, \big)$ on
the number of rounds required for computing the diameter $\delta$ of any
$n$-node network with quantum messages of size O$(\log n)$ in the CONGEST
model.
We draw a connection between the distributed computing scenario above and a
new model of query complexity. The information-theoretic technique we use for
deriving the round lower bound for Set Disjointness on a Line also applies to
the number of rounds in this query model. We provide an algorithm for Set
Disjointness in this query model with round complexity that matches the round
lower bound stated above, up to a polylogarithmic factor. This presents a
barrier for obtaining a better round lower bound for Set Disjointness on the
Line. At the same time, it hints at the possibility of better communication
protocols for the problem.
- Abstract（参考訳）: Set Disjointness on a Line は、$d+1$プロセッサが長さ$d$の経路に配置された分散コンピューティングシナリオにおける Set Disjointness 問題の変種である。
Le Gall と Magniez (PODC 2018) によって、CONGEST モデルにおける任意のネットワークの直径を計算する量子分散複雑性の低い境界を証明するために導入された。
しかし、パスの中間頂点でプロセッサが使用するローカルメモリが、n$-bit 入力で o$( \log n)$ qubits で構成される場合にのみ低いバウンドを提供することができた。
我々は、$d + 1$プロセッサを持つライン上の集合不整合のラウンドに対して、$\widetilde{\Omega}\big(\sqrt[3]{n d^2}+\sqrt{n} \, \big)$の条件のない下界を証明する。
その結果、$\widetilde{\Omega} \big( \sqrt[3]{n\delta^2}+\sqrt{n} \, \big)$の新たな下界が得られる。
我々は,上述の分散コンピューティングシナリオとクエリ複雑性の新しいモデルとの関連性について考察する。
ライン上の集合不整合のラウンド下界の導出に使用する情報理論技術は、このクエリモデルにおけるラウンド数にも適用される。
本稿では,この問合せモデルにおいて,上述のラウンド下界と一致するような複雑度を持つ集合不整合性のアルゴリズムを提案する。
これは、ライン上の集合不整合に対するより良い丸い下界を得るための障壁を示す。
同時に、この問題に対するより良い通信プロトコルの可能性も示唆している。
関連論文リスト
- Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity [22.615156512223763]
本研究では,有限サム構造を目的とする分散楽観的すべり(SVOGS)法を提案する。
我々は$mathcal O(delta D2/varepsilon)$、$mathcal O(n+sqrtndelta D2/varepsilon)$、$tildemathcal O(n+sqrtndelta+L)D2/varepsilon)$の局所呼び出しを証明している。
論文 参考訳（メタデータ） (2024-05-25T08:34:49Z) - Nearly-Optimal Consensus Tolerating Adaptive Omissions: Why is a Lot of Randomness Needed? [4.465134753953128]
同期分散システムにおいて,通信リンクから障害当事者への通信がメッセージの送信を省略できる場合,$n$の自律的パーティによる合意に達するという問題について検討する。
我々は、$O(sqrtnlog2 n)$ラウンドで動作し、$O(n2log3 n)$通信ビットを送信するランダム化アルゴリズムを設計する。
MCアルゴリズムが$O(R)$呼び出しを使用する場合、$Omega(fracn2maxR,nlog n)$ラウンドで動作しないことを示す。
論文 参考訳（メタデータ） (2024-05-08T02:17:10Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳（メタデータ） (2022-02-23T16:10:23Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - A Framework for Distributed Quantum Queries in the CONGEST Model [0.0]
量子クエリアルゴリズムを量子CONGESTで実装するための一般的なフレームワークを提供する。
分散Deutsch-Jozsa問題に対するプロトコルを一般化する。
また、サイクル検出と計算の問題を量子スピードアップする。
論文 参考訳（メタデータ） (2022-02-22T15:18:39Z) - Cut query algorithms with star contraction [4.570617424761779]
カットクエリを用いた単純なグラフのエッジ接続を決定する複雑さについて検討する。
エッジ接続を$O(n)$ cutクエリで計算する有界誤りランダム化アルゴリズムが存在することを示す。
また、$O(sqrtn)$ cutクエリでエッジ接続を計算する有界エラー量子アルゴリズムがあることも示している。
論文 参考訳（メタデータ） (2022-01-14T21:13:49Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳（メタデータ） (2021-07-22T14:25: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) - Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks [0.0]
直径の計算は分散計算における最も中心的な問題の1つである。
正確な直径計算のための$tilde O(sqrtnD)$-round量子分散アルゴリズムを示し、$D$は直径を表す。
これは、CONGESTモデルにおける量子アルゴリズムと古典アルゴリズムの計算能力の分離を示す。
論文 参考訳（メタデータ） (2018-04-09T11:24:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。