論文の概要: Optimal Low-Degree Hardness of Maximum Independent Set

• arxiv url: http://arxiv.org/abs/2010.06563v2
• Date: Thu, 12 Nov 2020 16:44:49 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-08 00:40:33.601118
• Title: Optimal Low-Degree Hardness of Maximum Independent Set
• Title（参考訳）: 最大独立集合の最適低次硬さ
• Authors: Alexander S. Wein
• Abstract要約: スパースな ErdHos-R'enyi ランダムグラフにおいて,大きな独立集合を求めるアルゴリズム的タスクについて検討する。 低次アルゴリズムのクラスは、半最適サイズの独立した集合を見つけることができるが、それ以上は見つからないことを示す。
• 参考スコア（独自算出の注目度）: 93.59919600451487
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the algorithmic task of finding a large independent set in a sparse Erd\H{o}s-R\'{e}nyi random graph with $n$ vertices and average degree $d$. The maximum independent set is known to have size $(2 \log d / d)n$ in the double limit $n \to \infty$ followed by $d \to \infty$, but the best known polynomial-time algorithms can only find an independent set of half-optimal size $(\log d / d)n$. We show that the class of low-degree polynomial algorithms can find independent sets of half-optimal size but no larger, improving upon a result of Gamarnik, Jagannath, and the author. This generalizes earlier work by Rahman and Vir\'ag, which proved the analogous result for the weaker class of local algorithms.
• Abstract（参考訳）: sparse erd\h{o}s-r\'{e}nyi ランダムグラフにおいて,n$ 頂点と平均次数 $d$ を持つ大きな独立集合を探索するアルゴリズム的タスクについて検討した。 最大独立集合は、2倍の極限で$(2 \log d / d)n$、次で$d \to \infty$を持つことが知られているが、最もよく知られている多項式時間アルゴリズムは、半最適サイズ$(\log d / d)n$の独立集合を見つけることができる。 低次多項式アルゴリズムのクラスは、半最適サイズの独立した集合を見つけることができるが、ガマルニク、ジャガンナス、および著者によって改善されることが示される。 これによりrahmanとvir\'agによる初期の研究が一般化され、局所アルゴリズムの弱いクラスに対する類似の結果が証明された。

関連論文リスト

• A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering [18.29151197560866]
  我々は[Makarychev, Makarychev and Vijayaraghavan, STOC'12] の半ランダムグラフモデルを考える。 時間アルゴリズムは、カットされた$(A, B)$がサイズ$Omega(alpha)$である限り、alphad Cutの問題を最大$O(alpha)$ [MMV'12]に近似することが知られている。 この問題の微細な複雑さについて検討し,[MMV'12]と同じような性能を示す最初のニア線形時間サブルーチンを提示する。
  論文  参考訳（メタデータ） (2024-06-07T11:40:54Z)
• The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs [0.0]
  低次アルゴリズムのクラスは、密度$left(fraclog d(r-1)dright)1/(r-1)$の独立した集合を見つけることができるが、それ以上は見つからない。 グラフケースは広く研究されているが、この研究はランダムなハイパーグラフ上の最適化問題の統計的-計算的ギャップを考える最初のものである。
  論文  参考訳（メタデータ） (2024-04-05T00:25:00Z)
• Do you know what q-means? [50.045011844765185]
  クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。 クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。 また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• 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)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

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

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