論文の概要: Improved Hardness of BDD and SVP Under Gap-(S)ETH

• arxiv url: http://arxiv.org/abs/2109.04025v3
• Date: Mon, 28 Jul 2025 22:24:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-03 20:19:02.807306
• Title: Improved Hardness of BDD and SVP Under Gap-(S)ETH
• Title（参考訳）: Gap-(S)ETHにおけるBDDとSVPの硬さの改善
• Authors: Huck Bennett, Chris Peikert, Yi Tang,
• Abstract要約: 我々は $ell_p$ ノルムにおける2つの鍵格子問題のきめ細かい硬さの改善を示す。 問題は、最小距離の$alpha$係数に境界距離デコードし、(決定的な)$gamma$-approximate Shortest Vector Problemを解くことである。
• 参考スコア（独自算出の注目度）: 6.876125456469918
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We show improved fine-grained hardness of two key lattice problems in the $\ell_p$ norm: Bounded Distance Decoding to within an $\alpha$ factor of the minimum distance ($\mathrm{BDD}_{p, \alpha}$) and the (decisional) $\gamma$-approximate Shortest Vector Problem ($\mathrm{SVP}_{p,\gamma}$), assuming variants of the Gap (Strong) Exponential Time Hypothesis (Gap-(S)ETH). Specifically, we show: 1. For all $p \in [1, \infty)$, there is no $2^{o(n)}$-time algorithm for $\mathrm{BDD}_{p, \alpha}$ for any constant $\alpha > \alpha_\mathsf{kn}$, where $\alpha_\mathsf{kn} = 2^{-c_\mathsf{kn}}$ and $c_\mathsf{kn}$ is the $\ell_2$ kissing-number constant, assuming $c_\mathsf{kn} > 0$ and that non-uniform Gap-ETH holds. 2. For all $p \in [1, \infty)$, there is no $2^{o(n)}$-time algorithm for $\mathrm{BDD}_{p, \alpha}$ for any constant $\alpha > \alpha^\ddagger_p$, where $\alpha^\ddagger_p$ is explicit and satisfies $\alpha^\ddagger_p = 1$ for $1 \leq p \leq 2$, $\alpha^\ddagger_p < 1$ for all $p > 2$, and $\alpha^\ddagger_p \to 1/2$ as $p \to \infty$, unless randomized Gap-ETH is false. 3. For all $p \in [1, \infty) \setminus 2 \mathbb{Z}$ and all $C > 1$, there is no $2^{n/C}$-time algorithm for $\mathrm{BDD}_{p, \alpha}$ for any constant $\alpha > \alpha^\dagger_{p, C}$, where $\alpha^\dagger_{p, C}$ is explicit and satisfies $\alpha^\dagger_{p, C} \to 1$ as $C \to \infty$ for any fixed $p \in [1, \infty)$, assuming $c_\mathsf{kn} > 0$ and that non-uniform Gap-SETH holds. 4. For all $p > p_0 \approx 2.1397$, $p \notin 2\mathbb{Z}$, and all $C > C_p$, there is no $2^{n/C}$-time algorithm for $\mathrm{SVP}_{p, \gamma}$ for some constant $\gamma > 1$, where $C_p > 1$ is explicit and satisfies $C_p \to 1$ as $p \to \infty$, unless randomized Gap-SETH is false.
• Abstract（参考訳）: 最小距離 (\mathrm{BDD}_{p, \alpha}$) と (決定的) の$\gamma$-approximate Shortest Vector Problem (\mathrm{SVP}_{p,\gamma}$) の$\alpha$因子の範囲内で、Gap (Strong) Exponential Time hypothesis (Gap-(S)ETH) の変項を仮定すると、$\mathrm{BDD}_{p, \alpha}$) と$\gamma$-approximate Shortest Vector Problem (\mathrm{SVP}_{p,\gamma}$) の2つの主要な格子問題のきめ細かい硬さが改善される。 特に、すべての$p \in [1, \infty)$に対して、$\mathrm{BDD}_{p, \alpha}$ for any constant $\alpha > \alpha_\mathsf{kn}$, where $\alpha_\mathsf{kn} = 2^{-c_\mathsf{kn}}$ and $c_\mathsf{kn}$ is the $\ell_2$ kissing-number constant, as as $c_\mathsf{kn} > 0$。 2. すべての$p \in [1, \infty)$に対して、$\mathrm{BDD}_{p, \alpha}$ for any constant $\alpha > \alpha^\ddagger_p$, where $\alpha^\ddagger_p$ is explicit and satisfies $\alpha^\ddagger_p = 1$ for $1 \leq p \leq 2$, $\alpha^\ddagger_p < 1$ for all $p > 2$, and $\alpha^\ddagger_p \to 1/2$ as $p \infty$。 3. すべての$p \in [1, \infty) \setminus 2 \mathbb{Z}$とすべての$C > 1$に対して、$\mathrm{BDD}_{p, \alpha}$-time algorithm for any constant $\alpha > \alpha^\dagger_{p, C}$は明示的で満足できる$\alpha^\dagger_{p, C} \to 1$ as $C \to \infty$ for any fixed $p \in [1, \infty)$, assuming $c_\mathsf{k} > 0, and non-unform Gap-THp は成り立たない。 すべての$p > p_0 \approx 2.1397$, $p \notin 2\mathbb{Z}$, and all $C > C_p$ に対して、ある定数 $\gamma > 1$ に対して$\mathrm{SVP}_{p, \gamma}$ が存在しない。

関連論文リスト

• Covering a Few Submodular Constraints and Applications [1.649938899766112]
  複数の部分モジュラー制約を網羅する問題を考察する。 任意の整数に対して$alpha ge 1$ が集合 $S$ を出力し、$f_i(S) ge$ 1-1/ealpha -epsilon)b_i$ が [r]$ と $mathbbE[c(S)] le (1+epsilon)alpha cdot sfOPT$ に対して$1-1/ealpha -epsilon)b_i$ が成り立つ。
  論文  参考訳（メタデータ） (2025-07-14T03:32:42Z)
• Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs [54.28273395444243]
  我々は,モノトニック値 Omega (MVP) アルゴリズムが,差分を考慮した差分依存残差境界を$tildeOleft(left(sum_Delta_h(s,a)>0 fracH2 log K land MathttVar_maxtextc$。
  論文  参考訳（メタデータ） (2025-06-06T20:33:57Z)
• Mind the Gap? Not for SVP Hardness under ETH! [2.682592098574199]
  指数時間仮説(ETH)に基づく基本格子問題に対する新しい硬さ結果の証明 まず、[1, infty)$ の任意の $p に対して、$mathsfCVP_p,gamma$ ($ell_p$-norm 近似ベクトル問題) が明示的な定数 $gamma > 1$ が存在することを示す。 次に、$mathsfSVP_p,gamma$ ($ell_p$-norm) のランダム化 ETH-hardness 結果を証明する。
  論文  参考訳（メタデータ） (2025-04-03T15:32:32Z)
• Sparsifying Suprema of Gaussian Processes [6.638504164134713]
  我々は、$O_varepsilon(1)$-size subset $S subseteq T$ と、S$ における実値 $c_s_s の集合が存在することを示す。 また、中心となるガウス過程の過度にスペーシフィケーション結果を用いて、有界な幾何学的幅の凸集合に対するスペーシフィケーション補題を与える。
  論文  参考訳（メタデータ） (2024-11-22T01:43:58Z)
• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。 我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
  論文  参考訳（メタデータ） (2024-10-07T19:47: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)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
  論文  参考訳（メタデータ） (2023-07-11T08:51:53Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• Terminal Embeddings in Sublinear Time [14.959896180728832]
  我々は、$T$を前処理して、サブ線形時間における$qinmathbbRd$の端末埋め込み画像の計算をサポートする、ほぼ線形空間のデータ構造を得る方法を示す。 この研究の主な貢献は、端末の埋め込みを計算するための新しいデータ構造を提供することです。
  論文  参考訳（メタデータ） (2021-10-17T00:50:52Z)
• Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
  任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
  論文  参考訳（メタデータ） (2021-09-21T13:19:04Z)
• Sets Clustering [25.358415142404752]
  我々は、$O(logn)$集合のコア集合が常に存在することを証明し、$O(nlogn)$ timeで計算することができる。 このコアセットに非効率だが最適なアルゴリズムを適用することで、集合-k$-means問題に対する最初のPTAS(1+varepsilon$ approximation)を得ることができる。 オープンソースコードと文書分類および施設位置の実験結果も提供される。
  論文  参考訳（メタデータ） (2020-03-09T13:30:30Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。