Fugu-MT 論文翻訳(概要): Solving Satisfiability of Polynomial Formulas By Sample-Cell Projection

論文の概要: Solving Satisfiability of Polynomial Formulas By Sample-Cell Projection

arxiv url: http://arxiv.org/abs/2003.00409v2
Date: Wed, 4 Mar 2020 03:01:35 GMT
ステータス: 処理完了
システム内更新日: 2022-12-27 13:22:42.643922
Title: Solving Satisfiability of Polynomial Formulas By Sample-Cell Projection
Title（参考訳）: サンプルセル投影による多項式公式の満足度
Authors: Haokun Li and Bican Xia
Abstract要約: 実数に対する公式の満足度を決定するアルゴリズムが提案されている。このアルゴリズムのキーポイントは、サンプルセルプロジェクション演算子と呼ばれる新しいプロジェクション演算子で、Conflict-Driven Clause Learning (CDCL)スタイルの検索用にカスタマイズされている。
参考スコア（独自算出の注目度）: 0.8702432681310401
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: A new algorithm for deciding the satisfiability of polynomial formulas over the reals is proposed. The key point of the algorithm is a new projection operator, called sample-cell projection operator, custom-made for Conflict-Driven Clause Learning (CDCL)-style search. Although the new operator is also a CAD (Cylindrical Algebraic Decomposition)-like projection operator which computes the cell (not necessarily cylindrical) containing a given sample such that each polynomial from the problem is sign-invariant on the cell, it is of singly exponential time complexity. The sample-cell projection operator can efficiently guide CDCL-style search away from conflicting states. Experiments show the effectiveness of the new algorithm.
Abstract（参考訳）: 実数上の多項式公式の充足可能性を決定する新しいアルゴリズムを提案する。このアルゴリズムのキーポイントは、サンプルセルプロジェクション演算子と呼ばれる新しいプロジェクション演算子であり、Conflict-Driven Clause Learning (CDCL)スタイルの検索用にカスタマイズされている。この新しい作用素は cad(cylindrical algebraic decomposition) のような射影作用素でもあるが、与えられたサンプルを含むセル(必ずしも円筒形ではない)を計算し、問題の多項式がセル上の符号不変である。サンプルセル投影演算子は、CDCLスタイルの探索を競合状態から効率的に誘導することができる。実験では,新しいアルゴリズムの有効性を示す。

関連論文リスト

Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文参考訳（メタデータ） (2024-03-08T18:50:19Z)
Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
本稿では, パール構造因果モデルにおいて, 因果関係などの部分的特定可能なクエリのバウンダリングの問題について議論する。最近提案された反復EMスキームは初期化パラメータをサンプリングしてそれらの境界を内部近似する。シンボルパラメータを実際の値に置き換えた回路構造を,単一のシンボル知識コンパイルによって得られることを示す。
論文参考訳（メタデータ） (2023-10-05T07:10:40Z)
An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文参考訳（メタデータ） (2023-09-30T15:57:14Z)
Best-Subset Selection in Generalized Linear Models: A Fast and Consistent Algorithm via Splicing Technique [0.6338047104436422]
ベストサブセットセクションは、このタイプの問題の聖杯として広く見なされている。軽度条件下での最適部分集合回復のためのアルゴリズムを提案し,提案した。我々の実装は、一般的な変数選択ツールキットと比較して約4倍のスピードアップを実現している。
論文参考訳（メタデータ） (2023-08-01T03:11:31Z)
Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
論文参考訳（メタデータ） (2023-04-01T15:50:18Z)
Alternatives to a nonhomogeneous partial differential equation quantum algorithm [52.77024349608834]
Apsi(textbfr)=f(textbfr)$ という形の非等質線型偏微分方程式を解くための量子アルゴリズムを提案する。これらの成果により、現代の技術に基づく量子アルゴリズムの実験的実装が容易になった。
論文参考訳（メタデータ） (2022-05-11T14:29:39Z)
Matrix Reordering for Noisy Disordered Matrices: Optimality and Computationally Efficient Algorithms [9.245687221460654]
単細胞生物学とメダゲノミクスの応用により,ノイズモノトンToeplitz行列モデルに基づく行列化の問題を考察した。我々は、決定理論の枠組みでこの問題の基本的な統計的限界を確立し、制約付き最小二乗率を示す。そこで本研究では,性能向上を保証した新しい時間適応ソートアルゴリズムを提案する。
論文参考訳（メタデータ） (2022-01-17T14:53:52Z)
Minimal Cycle Representatives in Persistent Homology using Linear Programming: an Empirical Study with User's Guide [4.46514714749204]
永続ホモロジークラスのサイクル代表は、データ内のトポロジ的特徴の説明に使用することができる。この問題を解決するためのアプローチの1つは、データのコンテキストで意味のある尺度に対して代表者の選択を最適化することです。
論文参考訳（メタデータ） (2021-05-14T18:38:48Z)
Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
論文参考訳（メタデータ） (2020-12-29T04:08:38Z)
A global-local neighborhood search algorithm and tabu search for flexible job shop scheduling problem [3.946442574906068]
この研究はGLNSA(Global-local neighborhood search algorithm)と呼ばれる新しいメタヒューリスティックアルゴリズムを提案する。提案アルゴリズムは,Nopt1地区の簡易版を実装したタブ検索と補完する。実験の結果,提案アルゴリズムの性能は,最近発表された他のアルゴリズムと比較すると良好であった。
論文参考訳（メタデータ） (2020-10-23T23:08:51Z)
Solution Path Algorithm for Twin Multi-class Support Vector Machine [6.97711662470035]
本論文は, ツインマルチクラスサポートベクトルマシンの高速正規化パラメータチューニングアルゴリズムについて述べる。新たなサンプルデータセット分割法を採用し,ラグランジアン乗算器は分数線形であることが証明された。提案手法は,グリッド探索手法の計算コストを指数レベルから定数レベルに削減し,優れた分類性能を実現する。
論文参考訳（メタデータ） (2020-05-30T14:05:46Z)

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