論文の概要: The Kikuchi Hierarchy is Sharp for $k$XOR
- arxiv url: http://arxiv.org/abs/2607.29672v1
- Date: Fri, 31 Jul 2026 17:54:11 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-03 14:29:40.83801
- Title: The Kikuchi Hierarchy is Sharp for $k$XOR
- Title（参考訳）: Kikuchi Hierarchyは$k$XORのシャープ
- Abstract要約: 菊池階層の正規化された変種は、対数損失のない鋭い予想されたトレードオフを、全てのアーティ$kge3$で達成することを示す。
また、同じモデルで一致した下界を証明し、推論と難解な上界はより一般的な植林法や述語に遷移する。
- 参考スコア（独自算出の注目度）: 46.26532142699448
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Planted noisy $k$XOR and the strong refutation of random $k$XOR are governed by a conjectured trade-off between signal strength and time: Level $\ell$ of the Kikuchi hierarchy should achieve the smooth curve \begin{equation*} m\ \gtrsim\ ρ^{-2}n^{k/2}/\ell^{k/2-1}\ \text{clauses} \quad\Longleftrightarrow\quad \text{solvable in time }n^{O(\ell)}, \end{equation*} where $ρ$ is the bias of the planted signal or, for refutation, the target advantage. However, every spectral analysis of sparse $k$XOR to date loses polylogarithmic factors against this curve, a loss that enters the exponent of the running time. We show that a normalized variant of the Kikuchi hierarchy achieves the sharp conjectured trade-off, with no logarithmic loss, at every arity $k\ge3$. At the scale above, our algorithms achieve strong detection, weak recovery, and strong refutation; an additional cleanup step boosts weak recovery to exact recovery, and the refutation certificates yield sum-of-squares proofs of degree $O_k(\ell)$. We also prove matching lower bounds in the same model. The inference and refutation upper bounds transfer to more general planting laws and predicates. Finally, we give a quantum algorithm that achieves a quartic speedup over the classical spectral algorithms for detection and weak recovery. The proofs rest on two key ingredients: a normalization of the sparse Kikuchi matrix, and a sharp count of the closed walks in its trace expansion. We use a closely related trace-walk count to prove Feige's 2008 hypergraph Moore bound conjecture in a companion paper.
- Abstract（参考訳）: キクチ階層のレベル$$\ell$は、滑らかな曲線 \begin{equation*} m\ \gtrsim\ ρ^{-2}n^{k/2}/\ell^{k/2-1}\ \text{clauses} \quad\Longleftrightarrow\quad \text{solvable in time }n^{O(\ell)}, \end{equation*} ここで$ρ$は、信号のバイアスであり、また、難読化のためにターゲットとなる。
しかし、現在までのスパース$k$XORのスペクトル解析は、この曲線に対して多対数的因子を失う。
菊池階層の正規化された変種は、対数損失のない鋭い予想されたトレードオフを、すべてのアーティ$k\ge3$で達成することを示す。
以上のスケールで、我々のアルゴリズムは、強い検出、弱い回復、強い難燃を達成する;追加のクリーンアップステップは、弱い回復を正確に回復させ、難燃証明書は、次数$O_k(\ell)$の2乗証明を得る。
また、同じモデルにおける下界のマッチングも証明する。
推論と難読化の上界はより一般的な植樹法や述語に移行する。
最後に、検出と弱い回復のための古典スペクトルアルゴリズムに対するクォート高速化を実現する量子アルゴリズムを提案する。
証明は、粗い菊池行列の正規化と、そのトレース展開におけるクローズドウォークの急激な数という2つの重要な要素に当てはまる。
我々は、ファイジの2008年のハイパーグラフムーア有界予想を共用論文で証明するために、密接に関連するトレースウォーク数を用いる。
関連論文リスト
- An Argmax Principle for Sum-of-Squares Relaxations on the Sphere [42.540924632302925]
単位球面上の最適化問題の総和緩和を解析するためのargmax原理を開発する。
私たちの指導原則は、最大値が丸みを帯びた候補であることです。
論文 参考訳（メタデータ） (2026-08-03T17:58:00Z) - A phase transition in the exactness of the NPA hierarchy at the critical doubly-tilted CHSH functional [0.0]
B_=langle A_0rangle+l B_0rangle+mathrmCHSH$。
すべての$,ge 1$とすべてのレベルで、階層は、アフィンのアイデンティティを実現する3つの明確な有理証明を通して、正確である。
サブクリティカル側では、正確な算術の最初の4つのレベルを認証する。
論文 参考訳（メタデータ） (2026-07-15T12:34:25Z) - Demixing Sparse Signals from Nonlinear Observations using Generalized Non-convex Regularization [0.0]
重畳の非線形観測回数が限られていることから, スパースベクトルの回復を考察する。
本稿では, 一般化畳み込みペナルティとハマー化データ忠実度を組み合わせた正規化に基づくフレームワークを提案する。
仮に局所的な定常点を保った位数$sqrtslog(n)/m$の誤差境界を導出する。
論文 参考訳（メタデータ） (2026-07-12T07:29:39Z) - Coupled Tensor-Matrix Recovery via Proximal Alternating Linearized Minimization, with an Application to Workforce Skill and Small-Business Health Estimation [0.0]
雑音観測から低ランクテンソル$mathcalT$と低ランク行列$M$の回復について検討した。
行列のみの問題に対しては、シーケンシャルな部分ケースに対して、サンプリング・複雑度が証明された結果を示す。
完備で交互に見積もった場合、予想を述べる。
論文 参考訳（メタデータ） (2026-07-11T07:06:08Z) - Near-Optimal Regret in Adversarial Kernel Bandits [50.68324062892194]
本稿では,各ラウンドにおける損失が任意の有界要素によって誘導される逆カーネルバンドイット問題について検討する。
我々の主な結果は、$widetildeObig(sqrtT, d_*(),log|X|big)$, ここでは$d_*()$は有効次元の広く解釈された概念である。
論文 参考訳（メタデータ） (2026-05-26T06:10:24Z) - Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。
これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
論文 参考訳（メタデータ） (2026-05-22T15:05:33Z) - The Marginal Problem for Density Operators [0.30079490585515334]
局所還元密度作用素が所定のマルコフ構造を持つ大域量子状態に組み立てられるかを検討する。
この障害がトレース条件によって正確に捕捉されていることを証明します。
3量子ビットのパウリの例は、量子障害物が実であることを示している。
論文 参考訳（メタデータ） (2026-05-19T07:06:54Z) - When Does $\ell_2$-Boosting Overfit Benignly? High-Dimensional Risk Asymptotics and the $\ell_1$ Implicit Bias [15.113649527486276]
良性オーバーフィッティングが線形レートで失敗することを示します。
この局所化機構は信号の存在下で持続するべきであるが、正確な信号-雑音分解は未解決の問題である。
論文 参考訳（メタデータ） (2026-05-07T14:14:09Z) - Hardness of High-Dimensional Linear Classification [58.29089693778071]
我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。
どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
論文 参考訳（メタデータ） (2026-03-19T15:53:41Z) - Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities [51.320599504997745]
統計物理学からの予測では、ブロックモデル(SBM)におけるコミュニティの回復は、上述の時間で可能であり、上述のケステンスティグム(KS)しきい値のみである。
Chinら(2025)は、最近、スパース体制では、非バックトラック経路を数えることにより、KS閾値以下でコミュニティの回復が可能であることを証明した。
論文 参考訳（メタデータ） (2025-09-19T09:53:56Z) - Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。
我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。
次に,新しい2段階クラスタリングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-06-02T05:10:40Z) - Convergence Rate Analysis of LION [54.28350823319057]
LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。
従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
論文 参考訳（メタデータ） (2024-11-12T11:30:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。