論文の概要: The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
- arxiv url: http://arxiv.org/abs/2404.03842v1
- Date: Fri, 5 Apr 2024 00:25:00 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-08 17:16:00.524994
- Title: The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
- Title（参考訳）: スパースランダムハイパーグラフにおける大規模独立集合の低次元硬さ
- Authors: Abhishek Dhawan, Yuzhou Wang,
- Abstract要約: 低次アルゴリズムのクラスは、密度$left(fraclog d(r-1)dright)1/(r-1)$の独立した集合を見つけることができるが、それ以上は見つからない。
グラフケースは広く研究されているが、この研究はランダムなハイパーグラフ上の最適化問題の統計的-計算的ギャップを考える最初のものである。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the algorithmic task of finding large independent sets in Erdos-Renyi $r$-uniform hypergraphs on $n$ vertices having average degree $d$. Krivelevich and Sudakov showed that the maximum independent set has density $\left(\frac{r\log d}{(r-1)d}\right)^{1/(r-1)}$. We show that the class of low-degree polynomial algorithms can find independent sets of density $\left(\frac{\log d}{(r-1)d}\right)^{1/(r-1)}$ but no larger. This extends and generalizes earlier results of Gamarnik and Sudan, Rahman and Virag, and Wein on graphs, and answers a question of Bal and Bennett. We conjecture that this statistical-computational gap holds for this problem. Additionally, we explore the universality of this gap by examining $r$-partite hypergraphs. A hypergraph $H=(V,E)$ is $r$-partite if there is a partition $V=V_1\cup\cdots\cup V_r$ such that each edge contains exactly one vertex from each set $V_i$. We consider the problem of finding large balanced independent sets (independent sets containing the same number of vertices in each partition) in random $r$-partite hypergraphs with $n$ vertices in each partition and average degree $d$. We prove that the maximum balanced independent set has density $\left(\frac{r\log d}{(r-1)d}\right)^{1/(r-1)}$ asymptotically. Furthermore, we prove an analogous low-degree computational threshold of $\left(\frac{\log d}{(r-1)d}\right)^{1/(r-1)}$. Our results recover and generalize recent work of Perkins and the second author on bipartite graphs. While the graph case has been extensively studied, this work is the first to consider statistical-computational gaps of optimization problems on random hypergraphs. Our results suggest that these gaps persist for larger uniformities as well as across many models. A somewhat surprising aspect of the gap for balanced independent sets is that the algorithm achieving the lower bound is a simple degree-1 polynomial.
- Abstract（参考訳）: 平均次数$d$の頂点上のエルドス=レーニ$r$ユニフォームハイパーグラフにおいて、大きな独立集合を求めるアルゴリズム的タスクについて検討する。
クリヴェレヴィチとスダコフは、最大独立集合は密度$\left(\frac{r\log d}{(r-1)d}\right)^{1/(r-1)}$であることを示した。
低次多項式アルゴリズムのクラスは、$\left(\frac{\log d}{(r-1)d}\right)^{1/(r-1)}$の独立した密度集合を見つけることができるが、それ以上は見つからない。
これはガマルニクとスーダン、ラーマンとヴィラグ、ワインのグラフに関する初期の結果を拡張し、一般化し、バルとベネットの質問に答える。
この統計計算のギャップがこの問題を補うと推測する。
さらに、このギャップの普遍性を$r$パーティイトハイパーグラフで調べる。
ハイパーグラフ $H=(V,E)$ が $r$-partite であるとき、分割 $V=V_1\cup\cdots\cup V_r$ が存在して、各エッジは各集合 $V_i$ からちょうど1つの頂点を含む。
各分割に$n$の頂点と平均次数$d$のランダムな$r$-partiteハイパーグラフにおいて、大きなバランスの取れた独立集合(各分割に同じ頂点数を含む独立集合)を見つけるという問題を考える。
最大平衡独立集合は密度$\left(\frac{r\log d}{(r-1)d}\right)^{1/(r-1)} を漸近的に持つことを証明している。
さらに、類似の低次計算しきい値が$\left(\frac{\log d}{(r-1)d}\right)^{1/(r-1)}$であることを証明する。
我々の結果は、パーキンスと二部グラフに関する2番目の著者の最近の業績を回復し、一般化する。
グラフケースは広く研究されているが、この研究はランダムなハイパーグラフ上の最適化問題の統計的-計算的ギャップを考える最初のものである。
以上の結果から,これらのギャップは,多くのモデルにまたがるより大きな均一性に対して持続することが示唆された。
バランスの取れた独立集合のギャップの幾分驚くべき側面は、下界を達成するアルゴリズムが単純な次数 1 多項式であることである。
関連論文リスト
- Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。
我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。
平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
論文 参考訳（メタデータ） (2023-04-17T10:38:08Z) - On the Unlikelihood of D-Separation [69.62839677485087]
解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。
PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。
UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
論文 参考訳（メタデータ） (2023-03-10T00:11:18Z) - Planted Bipartite Graph Detection [13.95780443241133]
ランダムグラフに隠れた二部グラフを検出するタスクについて検討する。
ヌル仮説の下では、このグラフは、エッジ密度$q$の$n$上のアードホスラーイランダムグラフの実現である。
k_mathsfR times k_mathsfL$ bipartite subgraph with edge density $p>q$。
論文 参考訳（メタデータ） (2023-02-07T18:18:17Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Fast Computation of Generalized Eigenvectors for Manifold Graph
Embedding [38.902986549367434]
我々は、高速実行に既存の高速極端固有ベクトル計算アルゴリズムを利用する。
我々の埋め込みは文献の中では最速であり、多様体グラフのクラスタリング性能は最高のものとなっている。
論文 参考訳（メタデータ） (2021-12-15T03:45:39Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Convergence of Graph Laplacian with kNN Self-tuned Kernels [14.645468999921961]
自己チューニングされたカーネルは、各点に$sigma_i$ を $k$-nearest neighbor (kNN) 距離で適応的に設定する。
本稿では、グラフラプラシアン作用素$L_N$を、kNN自己チューニングカーネルの新しい族に対する多様体(重み付き)ラプラシアンに収束することを証明する。
論文 参考訳（メタデータ） (2020-11-03T04:55:33Z) - Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
スパースな ErdHos-R'enyi ランダムグラフにおいて,大きな独立集合を求めるアルゴリズム的タスクについて検討する。
低次アルゴリズムのクラスは、半最適サイズの独立した集合を見つけることができるが、それ以上は見つからないことを示す。
論文 参考訳（メタデータ） (2020-10-13T17:26:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。