論文の概要: On Classifying Continuous Constraint Satisfaction Problems
- arxiv url: http://arxiv.org/abs/2106.02397v6
- Date: Sun, 14 Apr 2024 11:18:17 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-18 03:27:13.543215
- Title: On Classifying Continuous Constraint Satisfaction Problems
- Title（参考訳）: 連続制約満足度問題の分類について
- Authors: Tillmann Miltzow, Reinier F. Schmiermann,
- Abstract要約: 連続制約満足度問題 (CCSP) は制約満足度問題 (CSP) である。
我々は実数の実在論、すなわちER完全を完備とするCCSPを分類する。
そのような CCSP のクラス上では、曲線等式制約 (f(x,y) geq 0$ および $g(x,y) geq 0$) が ER 完全であることを示す。
- 参考スコア（独自算出の注目度）: 1.2277343096128712
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A continuous constraint satisfaction problem (CCSP) is a constraint satisfaction problem (CSP) with an interval domain $U \subset \mathbb{R}$. We engage in a systematic study to classify CCSPs that are complete of the Existential Theory of the Reals, i.e., ER-complete. To define this class, we first consider the problem ETR, which also stands for Existential Theory of the Reals. In an instance of this problem we are given some sentence of the form $\exists x_1, \ldots, x_n \in \mathbb{R} : \Phi(x_1, \ldots, x_n)$, where $\Phi$ is a well-formed quantifier-free formula consisting of the symbols $\{0, 1, +, \cdot, \geq, >, \wedge, \vee, \neg\}$, the goal is to check whether this sentence is true. Now the class ER is the family of all problems that admit a polynomial-time many-one reduction to ETR. It is known that NP $\subseteq$ ER $\subseteq$ PSPACE. We restrict our attention on CCSPs with addition constraints ($x + y = z$) and some other mild technical conditions. Previously, it was shown that multiplication constraints ($x \cdot y = z$), squaring constraints ($x^2 = y$), or inversion constraints ($x\cdot y = 1$) are sufficient to establish ER-completeness. We extend this in the strongest possible sense for equality constraints as follows. We show that CCSPs (with addition constraints and some other mild technical conditions) that have any one well-behaved curved equality constraint ($f(x,y) = 0$) are ER-complete. We further extend our results to inequality constraints. We show that any well-behaved convexly curved and any well-behaved concavely curved inequality constraint ($f(x,y) \geq 0$ and $g(x,y) \geq 0$) imply ER-completeness on the class of such CCSPs.
- Abstract（参考訳）: 連続制約満足度問題 (CCSP) は、間隔領域 $U \subset \mathbb{R}$ を持つ制約満足度問題(CSP)である。
我々は、現実の実在論、すなわちER完全を完備するCCSPを分類する体系的な研究に従事している。
このクラスを定義するために、我々はまず、実数実数実数理論(Existential Theory of the Reals)の略である ETR の問題を考察する。
この問題の例では、 $\exists x_1, \ldots, x_n \in \mathbb{R} : \Phi(x_1, \ldots, x_n)$, ここで、$\Phi$ は記号 $\{0, 1, +, \cdot, \geq, >, \wedge, \vee, \neg\}$ からなる十分に整形された量子化式である。
現在、クラス ER は多項式時間倍数 1 の ETR 還元を許容するすべての問題の族である。
NP $\subseteq$ ER $\subseteq$ PSPACE が知られている。
我々は、追加制約(x + y = z$)やその他の穏やかな技術的条件でCCSPに対する注意を制限します。
以前は、乗法制約(x \cdot y = z$)、スクアリング制約(x^2 = y$)、逆制約(x\cdot y = 1$)はER完全性を確立するのに十分であることが示された。
以下に、等式制約を最強の意味で拡張する。
CCSP (加法的制約およびその他の穏やかな技術的条件を含む) は、任意の曲線的等式制約 (f(x,y) = 0$) が ER 完全であることを示す。
結果をさらに不平等な制約にまで拡張します。
そのような CCSP のクラス上では、よく曲がった凸曲線や、よく曲がった凹凸不等式制約 (f(x,y) \geq 0$ および $g(x,y) \geq 0$) が ER 完全性を意味することを示す。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - CSPs with Few Alien Constraints [12.330326247154968]
CSP$(mathcalA cup mathcalB)$ ここで$mathcalA$は構造、$mathcalB$は異方構造である。
我々は、以前分類の試みを免れたいくつかのよく研究された問題に対して、接続を確立し、転送可能な複雑性結果を得る。
論文 参考訳（メタデータ） (2024-08-23T08:34:13Z) - Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳（メタデータ） (2024-06-07T08:26:31Z) - Statistical Query Lower Bounds for Learning Truncated Gaussians [43.452452030671694]
この問題のSQアルゴリズムの複雑さは、$dmathrmpoly (1/epsilon)$であり、クラス$mathcalC$が単純である場合でも、$mathrmpoly(d/epsilon)が情報理論的に十分であることを示す。
論文 参考訳（メタデータ） (2024-03-04T18:30:33Z) - 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) - A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of
Random CSPs [4.023424709659175]
制約あたり$k$変数(k-CSP)によるランダム制約満足度問題の強い反響を証明する。
割当数$p$の制約で満たされたランダムk-CSPインスタンスの場合、最適値が最大値$p+O_k(epsilon)$の制約で満足する証明書を効率的に計算できる。
論文 参考訳（メタデータ） (2022-04-20T16:21:21Z) - Near-Optimal Statistical Query Lower Bounds for Agnostically Learning
Intersections of Halfspaces with Gaussian Marginals [10.06689891744466]
本稿では,ガウス分布下での中間空間の学習に関するよく研究された問題について,難易度学習モデルを用いて考察する。
下界の2つの変種を証明し、それぞれがダイアコニコラスら (2021) の成分と、Boolean の設定に対する SQ 下界に対する異なる以前のアプローチ(拡張)を組み合わせた。
論文 参考訳（メタデータ） (2022-02-10T15:34:10Z) - Linear Bandits on Uniformly Convex Sets [88.3673525964507]
線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。
2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
論文 参考訳（メタデータ） (2021-03-10T07:33:03Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。
我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文 参考訳（メタデータ） (2020-06-29T17:10:10Z) - Some convergent results for Backtracking Gradient Descent method on
Banach spaces [0.0]
bf Theorem.$X$をバナッハ空間とし、$f:Xrightarrow mathbbR$を$C2$関数とする。
$mathcalC$ を $f$ の臨界点の集合とする。
論文 参考訳（メタデータ） (2020-01-16T12:49:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。