論文の概要: Mind the Gap? Not for SVP Hardness under ETH!

• arxiv url: http://arxiv.org/abs/2504.02695v1
• Date: Thu, 03 Apr 2025 15:32:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-04 12:54:57.572104
• Title: Mind the Gap? Not for SVP Hardness under ETH!
• Title（参考訳）: ギャップを忘れる?ETHの下でハードネスをSVPにしない!
• Authors: Divesh Aggarwal, Rishav Gupta, Aditya Morolia,
• Abstract要約: 指数時間仮説(ETH)に基づく基本格子問題に対する新しい硬さ結果の証明 まず、[1, infty)$ の任意の $p に対して、$mathsfCVP_p,gamma$ ($ell_p$-norm 近似ベクトル問題) が明示的な定数 $gamma > 1$ が存在することを示す。 次に、$mathsfSVP_p,gamma$ ($ell_p$-norm) のランダム化 ETH-hardness 結果を証明する。
• 参考スコア（独自算出の注目度）: 2.682592098574199
• License:
• Abstract: We prove new hardness results for fundamental lattice problems under the Exponential Time Hypothesis (ETH). Building on a recent breakthrough by Bitansky et al. [BHIRW24], who gave a polynomial-time reduction from $\mathsf{3SAT}$ to the (gap) $\mathsf{MAXLIN}$ problem-a class of CSPs with linear equations over finite fields-we derive ETH-hardness for several lattice problems. First, we show that for any $p \in [1, \infty)$, there exists an explicit constant $\gamma > 1$ such that $\mathsf{CVP}_{p,\gamma}$ (the $\ell_p$-norm approximate Closest Vector Problem) does not admit a $2^{o(n)}$-time algorithm unless ETH is false. Our reduction is deterministic and proceeds via a direct reduction from (gap) $\mathsf{MAXLIN}$ to $\mathsf{CVP}_{p,\gamma}$. Next, we prove a randomized ETH-hardness result for $\mathsf{SVP}_{p,\gamma}$ (the $\ell_p$-norm approximate Shortest Vector Problem) for all $p > 2$. This result relies on a novel property of the integer lattice $\mathbb{Z}^n$ in the $\ell_p$ norm and a randomized reduction from $\mathsf{CVP}_{p,\gamma}$ to $\mathsf{SVP}_{p,\gamma'}$. Finally, we improve over prior reductions from $\mathsf{3SAT}$ to $\mathsf{BDD}_{p, \alpha}$ (the Bounded Distance Decoding problem), yielding better ETH-hardness results for $\mathsf{BDD}_{p, \alpha}$ for any $p \in [1, \infty)$ and $\alpha > \alpha_p^{\ddagger}$, where $\alpha_p^{\ddagger}$ is an explicit threshold depending on $p$. We additionally observe that prior work implies ETH hardness for the gap minimum distance problem ($\gamma$-$\mathsf{MDP}$) in codes.
• Abstract（参考訳）: 指数時間仮説 (ETH) の下で, 基本格子問題に対する新しい硬さ結果を示す。 Bitansky et al [BHIRW24] による最近のブレークスルーに基づいて、彼は多項式時間を$\mathsf{3SAT}$から (gap) $\mathsf{MAXLIN}$ problem-a class of CSPs with linear equations over finite field-we derive ETH-hardness for several lattice problem。 まず、任意の$p \in [1, \infty)$に対して、明示的な定数 $\gamma > 1$ {\displaystyle $\mathsf{CVP}_{p,\gamma}$ ($\ell_p$-norm Nearst Vector Problem) が存在し、ETH が偽でない限り 2^{o(n)}$-time アルゴリズムは認められないことを示す。 我々の還元は決定論的であり、(gap)$\mathsf{MAXLIN}$から$\mathsf{CVP}_{p,\gamma}$への直接還元によって進行する。 次に、すべての$p > 2$ に対して $\mathsf{SVP}_{p,\gamma}$ ($\ell_p$-norm 近似した最短ベクトル問題) に対してランダム化された ETH-ハードネス結果を証明する。 この結果は、$\ell_p$ノルムにおける整数格子 $\mathbb{Z}^n$ の新たな性質と、$\mathsf{CVP}_{p,\gamma}$ から$\mathsf{SVP}_{p,\gamma'}$ へのランダム化還元に依存する。 最後に、$\mathsf{3SAT}$から$\mathsf{BDD}_{p, \alpha}$(境界距離復号問題)への事前還元よりも改善し、$\mathsf{BDD}_{p, \alpha}$ for any $p \in [1, \infty)$および$\alpha > \alpha_p^{\ddagger}$に対して、$\alpha_p^{\ddagger}$は$p$に依存する明示的なしきい値である。 さらに、事前の作業は、符号におけるギャップ最小距離問題(英語版)(\gamma$-$\mathsf{MDP}$)に対するETH硬さを意味する。

関連論文リスト

• Algorithmic contiguity from low-degree conjecture and applications in correlated random graphs [0.0]
  2つの問題に対して計算硬度を示す。 我々の証明の主な要素の1つは、2つの確率測度の間の近位関係を導出することである。 このフレームワークは、異なるタスク間のリダクションを実行するための便利なツールを提供する。
  論文  参考訳（メタデータ） (2025-02-14T00:24:51Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• 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)
• Sample-Efficient Linear Regression with Self-Selection Bias [7.605563562103568]
  未知のインデックス設定における自己選択バイアスを伴う線形回帰の問題を考察する。 我々は,$mathbfw_1,ldots,mathbfw_kinを復元する,新しい,ほぼ最適なサンプル効率($k$)アルゴリズムを提案する。 このアルゴリズムは雑音の仮定をかなり緩めることに成功し、従って関連する最大線形回帰の設定にも成功している。
  論文  参考訳（メタデータ） (2024-02-22T02:20:24Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• A Nearly-Optimal Bound for Fast Regression with $\ell_\infty$ Guarantee [16.409210914237086]
  行列 $Ain mathbbRntimes d$ とテンソル $bin mathbbRn$ が与えられたとき、 $ell_infty$ の回帰問題を考える。 このような$ell_infty$レグレッションの保証を得るためには、濃密なスケッチ行列を使わなければならない。 我々はまた、OCE(Oblivious Coordinate-wise Embedding)特性を利用した $ell_infty$ guarantee regression のための新しい分析フレームワークを開発した。
  論文  参考訳（メタデータ） (2023-02-01T05:22:40Z)
• Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
  マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。 我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
  論文  参考訳（メタデータ） (2022-07-28T17:50:53Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Algorithms and Hardness for Linear Algebra on Geometric Graphs [14.822517769254352]
  グリーンガードとロークリンの有名な高速多重極法における次元$dの指数的依存は改善できないことを示す。 これは高速多重極法について証明された最初の公式な制限である。
  論文  参考訳（メタデータ） (2020-11-04T18:35:02Z)

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

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