Fugu-MT 論文翻訳(概要): The Long, the Short and the Random

論文の概要: The Long, the Short and the Random

arxiv url: http://arxiv.org/abs/2011.01649v2
Date: Sun, 8 Nov 2020 22:39:15 GMT
ステータス: 処理完了
システム内更新日: 2022-09-30 05:54:26.240487
Title: The Long, the Short and the Random
Title（参考訳）: 長、短、ランダム
Authors: Giorgio Camerani
Abstract要約: アルゴリズムは、サブ指数時間における満足な割り当ての正確なカウントを計算する。このアルゴリズムは、すべてのCNF式が持つ優れた性質を使い、不満足な代入の個数をモノトーン部分形式の空間に関連付けている。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We furnish solid evidence, both theoretical and empirical, towards the existence of a deterministic algorithm for random sparse $\#\Omega(\log n)$-SAT instances, which computes the exact counting of satisfying assignments in sub-exponential time. The algorithm uses a nice combinatorial property that every CNF formula has, which relates its number of unsatisfying assignments to the space of its monotone sub-formulae.
Abstract（参考訳）: 我々は,確率スパース$\#\Omega(\log n)$-SATインスタンスに対する決定論的アルゴリズムの存在に対して,理論的かつ実証的な確固たる証拠を提示する。このアルゴリズムは、すべてのCNF式が持つ優れた組合せ特性を使い、その単調な部分形式の空間に対する不満足な割り当ての数に関連する。

関連論文リスト

Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文参考訳（メタデータ） (2024-08-14T19:04:13Z)
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)
Scalable network reconstruction in subquadratic time [0.0]
本稿では,この2次ベースラインを大幅に上回る広範囲の再構成問題に適用可能な一般アルゴリズムを提案する。我々のアルゴリズムは、高い確率で最適なエッジ候補を生成する第2の隣人探索に依存している。本アルゴリズムは2次ベースラインよりも桁違いに高速な性能を実現する。
論文参考訳（メタデータ） (2024-01-02T19:00:13Z)
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)
Approximating a RUM from Distributions on k-Slates [88.32814292632675]
与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
論文参考訳（メタデータ） (2023-05-22T17:43:34Z)
Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文参考訳（メタデータ） (2023-02-16T13:57:19Z)
Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文参考訳（メタデータ） (2023-01-11T09:12: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)
Efficient One Sided Kolmogorov Approximation [7.657378889055477]
本研究の主な応用は, 時系列並列スケジュールにおいて, 欠落する確率を推定することである。これらの確率の正確な計算はNPハードであるため,本論文で記述したアルゴリズムを用いて近似を求める。
論文参考訳（メタデータ） (2022-07-14T10:03:02Z)
Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文参考訳（メタデータ） (2022-06-07T16:49:54Z)
Complexity of zigzag sampling algorithm for strongly log-concave distributions [6.336005544376984]
強いログ凹分布に対するジグザグサンプリングアルゴリズムの計算複雑性について検討する。ジグザグサンプリングアルゴリズムは, 計算コストが$obiglに匹敵するchi-squareの発散において, $varepsilon$ 誤差を達成することを証明した。
論文参考訳（メタデータ） (2020-12-21T03:10:21Z)

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