論文の概要: A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of
Random CSPs
- arxiv url: http://arxiv.org/abs/2204.10881v1
- Date: Wed, 20 Apr 2022 16:21:21 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-01 08:51:02.415015
- Title: A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of
Random CSPs
- Title（参考訳）: 非ブール行列に対するIhara-Bass式とランダムCSPの強い反発
- Authors: Tommaso d'Orsi, Luca Trevisan
- Abstract要約: 我々は、任意の対称行列に付随する「非バックトラック」行列の概念を定義する。
ランダムな制約満足度問題に対する強い反発に対する新しい結果を示す。
改善は多言語性に過ぎませんが、この種の結果に対する大きな障壁を克服しています。
- 参考スコア（独自算出の注目度）: 4.023424709659175
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We define a notion of "non-backtracking" matrix associated to any symmetric
matrix, and we prove a "Ihara-Bass" type formula for it. Previously, these
notions were known only for symmetric 0/1 matrices.
We use this theory to prove new results on polynomial-time strong refutations
of random constraint satisfaction problems with $k$ variables per constraints
(k-CSPs). For a random k-CSP instance constructed out of a constraint that is
satisfied by a $p$ fraction of assignments, if the instance contains $n$
variables and $n^{k/2} / \epsilon^2$ constraints, we can efficiently compute a
certificate that the optimum satisfies at most a $p+O_k(\epsilon)$ fraction of
constraints.
Previously, this was known for even $k$, but for odd $k$ one needed $n^{k/2}
(\log n)^{O(1)} / \epsilon^2$ random constraints to achieve the same
conclusion.
Although the improvement is only polylogarithmic, it overcomes a significant
barrier to these types of results. Strong refutation results based on current
approaches construct a certificate that a certain matrix associated to the
k-CSP instance is quasirandom. Such certificate can come from a Feige-Ofek type
argument, from an application of Grothendieck's inequality, or from a spectral
bound obtained with a trace argument. The first two approaches require a union
bound that cannot work when the number of constraints is $o(n^{\lceil k/2
\rceil})$ and the third one cannot work when the number of constraints is
$o(n^{k/2} \sqrt{\log n})$.
- Abstract（参考訳）: 我々は、任意の対称行列に付随する「非バックトラッキング」行列の概念を定義し、それに対する「イハラバス」型公式を証明した。
以前は、これらの概念は対称 0/1 行列に対してのみ知られていた。
この理論を用いて,制約当たり$k$変数 (k-csps) を持つ無作為制約満足度問題の多項式時間強い反論を証明した。
代入分数$p$で満たされる制約で構築されたランダムk-CSPインスタンスに対して、もしインスタンスに$n$変数と$n^{k/2} / \epsilon^2$制約があるなら、最適値が少なくとも$p+O_k(\epsilon)$制約分で満足する証明書を効率的に計算できる。
以前は$k$でも知られていたが、奇数$k$の場合、同じ結論を達成するために$n^{k/2} (\log n)^{O(1)} / \epsilon^2$ランダムな制約が必要であった。
改善は多対数に過ぎませんが、この種の結果に対する大きな障壁を克服します。
現在のアプローチに基づく強い反発の結果は、k-CSPインスタンスに関連するある行列が準ランダムであることの証明を構築する。
そのような証明は、ファイゲ=オフェック型の引数、グロタンディークの不等式の適用、あるいはトレース引数で得られるスペクトル境界から得られる。
最初の2つのアプローチでは、制約の数が$o(n^{\lceil k/2 \rceil})$であり、3番目のアプローチは、制約の数が$o(n^{k/2} \sqrt{\log n})$であるときに機能しないユニオン境界を必要とする。
関連論文リスト
- Monge-Kantorovich Fitting With Sobolev Budgets [6.748324975906262]
近似の性能をMonge-Kantorovich $p$-costで定量化する。
次に、ソボレフ予算の制約の下で、機能的$mathscrJ_p(f)$を最小化するものとして問題を再構築する。
論文 参考訳（メタデータ） (2024-09-25T01:30:16Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Efficient Quantum State Synthesis with One Query [0.0]
本稿では,古典的オラクルへの単一クエリ(重ね合わせ)を実現する時間類似量子アルゴリズムを提案する。
我々は、すべての$n$-qubit状態が、適切な有限ゲート集合上の$On/n)$-size回路によって0.01エラー内に構築可能であることを証明した。
論文 参考訳（メタデータ） (2023-06-02T17:49:35Z) - Towards Characterizing the First-order Query Complexity of Learning
(Approximate) Nash Equilibria in Zero-sum Matrix Games [0.0]
正確な平衡は$O(fracln Kepsilon)$クエリの代わりに$O(fracln Kepsilon)$から効率的に計算できることを示す。
我々は下界に対する新しい手法を導入し、任意の$epsilon leq 1 / (cK4)$に対して$tildeOmega(frac1Kepsilon)$の下位境界を得ることができる。
論文 参考訳（メタデータ） (2023-04-25T12:42:59Z) - Average-Case Complexity of Tensor Decomposition for Low-Degree
Polynomials [93.59919600451487]
多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。
1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。
テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
論文 参考訳（メタデータ） (2022-11-10T00:40:37Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳（メタデータ） (2022-02-23T16:10:23Z) - On Classifying Continuous Constraint Satisfaction Problems [1.2277343096128712]
連続制約満足度問題 (CCSP) は制約満足度問題 (CSP) である。
我々は実数の実在論、すなわちER完全を完備とするCCSPを分類する。
そのような CCSP のクラス上では、曲線等式制約 (f(x,y) geq 0$ および $g(x,y) geq 0$) が ER 完全であることを示す。
論文 参考訳（メタデータ） (2021-06-04T10:23:48Z) - $k$-Forrelation Optimally Separates Quantum and Classical Query
Complexity [3.4984289152418753]
我々は、$N$ビット上の任意の部分関数は、$q$量子クエリを作れば、ランダムな推測よりも$delta$で計算できることを示した。
我々はまた、$k$-Forrelation問題 -- $q = lceil k/2 rceil$量子クエリで計算できる部分関数 -- を予想した。
論文 参考訳（メタデータ） (2020-08-16T21:26:46Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。