論文の概要: The Algorithmic Phase Transition of Random $k$-SAT for Low Degree
Polynomials
- arxiv url: http://arxiv.org/abs/2106.02129v1
- Date: Thu, 3 Jun 2021 21:01:02 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-07 14:46:00.347181
- Title: The Algorithmic Phase Transition of Random $k$-SAT for Low Degree
Polynomials
- Title（参考訳）: 低次多項式に対するランダム$k$-SATのアルゴリズム的相転移
- Authors: Guy Bresler, Brice Huang
- Abstract要約: 満足な代入は、節密度$m/n 2k log 2 - frac12で高い確率で存在することが知られている。
低次アルゴリズムは節密度$(1 - o_k(1)) 2k log k / k$で満足な代入を見つけることができる。
- 参考スコア（独自算出の注目度）: 18.00315760946089
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Let $\Phi$ be a uniformly random $k$-SAT formula with $n$ variables and $m$
clauses. We study the algorithmic task of finding a satisfying assignment of
$\Phi$. It is known that a satisfying assignment exists with high probability
at clause density $m/n < 2^k \log 2 - \frac12 (\log 2 + 1) + o_k(1)$, while the
best polynomial-time algorithm known, the Fix algorithm of Coja-Oghlan, finds a
satisfying assignment at the much lower clause density $(1 - o_k(1)) 2^k \log k
/ k$. This prompts the question: is it possible to efficiently find a
satisfying assignment at higher clause densities?
To understand the algorithmic threshold of random $k$-SAT, we study low
degree polynomial algorithms, which are a powerful class of algorithms
including Fix, Survey Propagation guided decimation, and paradigms such as
message passing and local graph algorithms. We show that low degree polynomial
algorithms can find a satisfying assignment at clause density $(1 - o_k(1)) 2^k
\log k / k$, matching Fix, and not at clause density $(1 + o_k(1)) \kappa^* 2^k
\log k / k$, where $\kappa^* \approx 4.911$. This shows the first sharp (up to
constant factor) computational phase transition of random $k$-SAT for a class
of algorithms. Our proof establishes and leverages a new many-way overlap gap
property tailored to random $k$-SAT.
- Abstract（参考訳）: $\phi$を一様ランダムな$k$-sat公式とし、$n$変数と$m$節を持つ。
満足度の高い$\Phi$を求めるアルゴリズムタスクについて検討する。
条件密度 $m/n < 2^k \log 2 - \frac12 (\log 2 + 1) + o_k(1)$ で高い確率で満足する代入が存在することが知られているが、最も優れた多項式時間アルゴリズムである coja-oghlan の固定アルゴリズムは、非常に低い節密度 $(1 - o_k(1)) 2^k \log k / k$ で満足する代入を見つける。
より高い節密度で満足度の高い代入を効率的に見つけることは可能か?
ランダムな$k$-SATのアルゴリズムしきい値を理解するために、Fix, Survey Propagation guided decimation, メッセージパッシングや局所グラフアルゴリズムなどのパラダイムを含むアルゴリズムの強力なクラスである低次多項式アルゴリズムについて検討する。
低次多項式アルゴリズムは、節密度$(1 - o_k(1)) 2^k \log k / k$, matching Fix, not at clause density$(1 + o_k(1)) \kappa^* 2^k \log k / k$, where $\kappa^* \approx 4.911$で満足な代入を見つけることができる。
これは、アルゴリズムのクラスに対するランダムな$k$-satの最初の鋭い(定数まで)計算位相遷移を示している。
我々の証明は、ランダムな$k$-SATに合わせて、新しい多方向重複ギャップ特性を確立し、活用する。
関連論文リスト
- Local Quantum Search Algorithm for Random $k$-SAT with $Ω(n^{1+ε})$ Clauses [0.0]
平均ケース複雑性理論に基づいて,$m=Omega(n2+delta+epsilon)$のとき,max-k-SSAT が平均計算アルゴリズムであることを示す。
また、平均ケース複雑性理論に基づいて$m=Omega(n2+delta+epsilon)$のとき、max-k-SSATが平均であることが証明される。
論文 参考訳（メタデータ） (2024-03-05T15:03:47Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Algoritmo de Contagem Qu\^antico Aplicado ao Grafo Bipartido Completo [0.0]
Groverのアルゴリズムは、$O(sqrtN/k)$ stepsを使って$N$要素を持つ、順序のないデータベースで$k$要素を見つけることができる。
この研究は、他のグラフのマーク要素の値$k$を推定するために量子カウントアルゴリズムを使用する問題に取り組む。
論文 参考訳（メタデータ） (2023-12-05T21:15:09Z) - 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) - 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) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Near-Optimal Lower Bounds For Convex Optimization For All Orders of
Smoothness [26.71898403195793]
非常に滑らかな凸関数を最適化する複雑性について検討する。
正の整数 $p$ に対して、凸関数 $f$ の最小値 $epsilon$-approximate を求める。
我々は、この境界(ログファクタまで)にマッチする新しい下界を証明し、ランダム化アルゴリズムだけでなく、量子アルゴリズムにも適用する。
論文 参考訳（メタデータ） (2021-12-02T10:51:43Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - Classical algorithms and quantum limitations for maximum cut on
high-girth graphs [6.262125516926276]
すべての(量子または古典的な)一局所アルゴリズムが$D$正規グラフに対して$5$の最大カットが1/2 + C/sqrtD$ for $C=1/sqrt2 approx 0.7071$であることを示す。
1/2 + C/sqrtD - O (1/sqrtk)$ for $D$-regular graphs of $> 2k+1$,
論文 参考訳（メタデータ） (2021-06-10T16:28:23Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。