論文の概要: On Classifying Continuous Constraint Satisfaction problems
- arxiv url: http://arxiv.org/abs/2106.02397v1
- Date: Fri, 4 Jun 2021 10:23:48 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-07 23:08:19.917574
- Title: On Classifying Continuous Constraint Satisfaction problems
- Title(参考訳): 連続制約満足度問題の分類について
- Authors: Tillmann Miltzow and Reinier F. Schmiermann
- Abstract要約: 連続制約満足度問題 (CCSP) は、領域 $U の部分集合 mathbbR$ を持つ制約満足度問題 (CSP) である。
我々は実数の実在論、すなわちER完全を完備とするCCSPを分類する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A continuous constraint satisfaction problem (CCSP) is a constraint
satisfaction problem (CSP) with a 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 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 condition. 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 condition) 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.
We apply our findings to geometric packing and answer an open question by
Abrahamsen et al. [FOCS 2020]. Namely, we establish ER-completeness of packing
convex pieces into a square container under rotations and translations.
- Abstract(参考訳): 連続制約満足度問題 (CCSP) は、領域 $U \subset \mathbb{R}$ を持つ制約満足度問題(CSP)である。
我々は実数の存在論的理論、すなわち er-complete の完全な ccsps を分類する体系的な研究を行っている。
このクラスを定義するために、まず、実数の存在論的理論を表す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 は ETR への多項式時間還元を認めるすべての問題の族である。
NP $\subseteq$ ER $\subseteq$ PSPACE が知られている。
我々は、追加制約(x + y = z$)およびその他の穏やかな技術的条件でCCSPに対する注意を制限する。
以前は、乗法制約(x \cdot y = z$)、スクアリング制約(x^2 = y$)、逆制約(x\cdot y = 1$)はER完全性を確立するのに十分であることが示された。
平等の制約に対して最も強い意味でこれを拡張します。
CCSP (加法的制約およびその他の穏やかな技術的条件を含む) は1つの有向曲線等式制約(f(x,y) = 0$)が ER 完全であることを示す。
我々はさらに不平等な制約に結果を広げる。
任意の凸凸曲線および凸曲線不等式制約 (f(x,y) \geq 0$ および $g(x,y) \geq 0$) は、そのようなccspのクラスにおけるer完全性を示す。
我々はこの知見を幾何学的パッキングに適用し,abrahamsenらによる公開質問に答える。
〔forcs 2020〕
すなわち、回転および変換の下で凸片を正方形容器に充填するER完全性を確立する。
関連論文リスト
- Statistical Query Lower Bounds for Learning Truncated Gaussians [43.452452030671694]
この問題のSQアルゴリズムの複雑さは、$dmathrmpoly (1/epsilon)$であり、クラス$mathcalC$が単純である場合でも、$mathrmpoly(d/epsilon)が情報理論的に十分であることを示す。
論文 参考訳(メタデータ) (2024-03-04T18:30:33Z) - SQ Lower Bounds for Learning Single Neurons with Massart Noise [40.1662767099183]
マスアートノイズの存在下で単一ニューロンを学習するPAC。
我々は、任意の定数係数内で最適な誤差を近似できる効率的なSQアルゴリズムが存在しないことを証明した。
論文 参考訳(メタデータ) (2022-10-18T15:58:00Z) - 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) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳(メタデータ) (2021-08-19T16:16:48Z) - 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) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳(メタデータ) (2020-02-17T18:41:49Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。