論文の概要: 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完全性を確立する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。