論文の概要: Is the space complexity of planted clique recovery the same as that of detection?

• arxiv url: http://arxiv.org/abs/2008.12825v2
• Date: Mon, 23 Nov 2020 23:44:57 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-24 02:43:48.389355
• Title: Is the space complexity of planted clique recovery the same as that of detection?
• Title（参考訳）: 植林した傾斜回復の空間的複雑さは検出の時と同じか?
• Authors: Jay Mardia
• Abstract要約: エルドホス=レーニイグラフ G(n, 1/2) に大きさ k の大きさの斜めが植えられる植込み斜め問題について検討する。 この問題は、clique size k=sqrtnで統計計算のギャップを示すと広く信じられているため興味深い。 k=Omega(sqrtn) の場合、回復問題は空間の O((log*n-log*k/sqrtn) log n) ビットで解くことができる。
• 参考スコア（独自算出の注目度）: 1.9290392443571387
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the planted clique problem in which a clique of size k is planted in an Erd\H{o}s-R\'enyi graph G(n, 1/2), and one is interested in either detecting or recovering this planted clique. This problem is interesting because it is widely believed to show a statistical-computational gap at clique size k=sqrt{n}, and has emerged as the prototypical problem with such a gap from which average-case hardness of other statistical problems can be deduced. It also displays a tight computational connection between the detection and recovery variants, unlike other problems of a similar nature. This wide investigation into the computational complexity of the planted clique problem has, however, mostly focused on its time complexity. In this work, we ask- Do the statistical-computational phenomena that make the planted clique an interesting problem also hold when we use `space efficiency' as our notion of computational efficiency? It is relatively easy to show that a positive answer to this question depends on the existence of a O(log n) space algorithm that can recover planted cliques of size k = Omega(sqrt{n}). Our main result comes very close to designing such an algorithm. We show that for k=Omega(sqrt{n}), the recovery problem can be solved in O((log*{n}-log*{k/sqrt{n}}) log n) bits of space. 1. If k = omega(sqrt{n}log^{(l)}n) for any constant integer l > 0, the space usage is O(log n) bits. 2.If k = Theta(sqrt{n}), the space usage is O(log*{n} log n) bits. Our result suggests that there does exist an O(log n) space algorithm to recover cliques of size k = Omega(sqrt{n}), since we come very close to achieving such parameters. This provides evidence that the statistical-computational phenomena that (conjecturally) hold for planted clique time complexity also (conjecturally) hold for space complexity.
• Abstract（参考訳）: 我々は、大きさ k のclique を Erd\H{o}s-R\'enyi graph G(n, 1/2) に植込み、このclique を検出または回収することに関心がある。 この問題は、クランクサイズ k=sqrt{n} における統計計算的ギャップが広く信じられており、他の統計問題の平均ケース硬度を推定できるようなギャップを持つ原型的問題として浮上している。 また、同様の性質の他の問題とは異なり、検出と回復の変種間の密接な計算的接続を示す。 しかし、植えられたクランク問題の計算複雑性に関するこの広範囲な調査は、主に時間複雑性に焦点が当てられている。 本研究では, 「空間効率」 を計算効率の概念として用いる場合, 植栽されたクライクを興味深い問題にするための統計的計算現象を問う。 この問題に対する肯定的な答えは、サイズ k = Omega(sqrt{n}) の植込みクリケットを復元できる O(log n) 空間アルゴリズムの存在に依存することを示すことは比較的容易である。 私たちの主な成果は,そのようなアルゴリズムの設計に非常に近いものです。 k=Omega(sqrt{n}) の場合、回復問題は空間の O((log*{n}-log*{k/sqrt{n}}) log n) ビットで解くことができる。 1. 任意の定数整数 l > 0 に対して k = omega(sqrt{n}log^{(l)}n) であれば、空間利用は O(log n) ビットである。 2. k = theta(sqrt{n}) ならば、空間の使い方は o(log*{n} log n) ビットである。 この結果は、そのようなパラメータの達成に非常に近いため、サイズ k = Omega(sqrt{n}) の傾きを回復するための O(log n) 空間アルゴリズムが存在することを示唆している。 これは、(仮定的に)植木されたクランクの時間複雑性を(仮定的に)保持する統計計算現象が、(仮定的に)空間複雑性をも保持する証拠を与える。

関連論文リスト

• Data subsampling for Poisson regression with pth-root-link [53.63838219437508]
  ポアソン回帰のためのデータサブサンプリング手法を開発し解析する。 特に,ポアソン一般化線形モデルと ID-および平方根リンク関数について考察する。
  論文  参考訳（メタデータ） (2024-10-30T10:09:05Z)
• Agnostic Membership Query Learning with Nontrivial Savings: New Results, Techniques [0.0]
  学習の最前線で授業の会員クエリによる学習を検討する。 このアプローチは、非自明な貯蓄を伴う線形学習の研究にインスパイアされ、継続する」。 ゲートのサブ線形数からなる回路の非依存学習アルゴリズムを確立する。
  論文  参考訳（メタデータ） (2023-11-11T23:46:48Z)
• 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)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。 我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
  論文  参考訳（メタデータ） (2023-06-28T16:33:39Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。 低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
  論文  参考訳（メタデータ） (2023-02-13T22:51:07Z)
• Verification and search algorithms for causal DAGs [11.038866111306728]
  クレーム因果グラフの正しさを確認するために、最小サイズの原子介入のセットを特徴づける。 我々は,ノード依存の介入コストと境界サイズ介入の設定に対して,その結果を一般化する。 この結果は、一般の未重み付きグラフ上での検証サイズに対する非自明な近似を保証する最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2022-06-30T15:52:30Z)
• Logspace Reducibility From Secret Leakage Planted Clique [0.9427635404752933]
  植民された傾斜問題は、計算現象を観察し、説明し、予測する文脈でよく研究されている。 この問題は、他の多くの統計問題のホストの計算困難さを推測するために用いられる。
  論文  参考訳（メタデータ） (2021-07-25T20:33:15Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。 具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。 ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-22T11:07:38Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case [6.810856082577402]
  量子回路は、グラフの局所性を尊重するユニタリ作用素の p 個の応用を持つ。 我々は、d と n を大きく保った dn/2 エッジを持つランダムグラフにおいて、大きな独立集合を見つけることに集中する。
  論文  参考訳（メタデータ） (2020-04-20T00:48:02Z)

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

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