論文の概要: Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices

• arxiv url: http://arxiv.org/abs/2410.02636v3
• Date: Tue, 24 Jun 2025 21:51:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-26 14:36:54.685175
• Title: Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices
• Title（参考訳）: 符号, 部分空間, 格子におけるスパースベクトルの非近似性
• Authors: Vijay Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee, Xuandi Ren,
• Abstract要約: スパースベクトルを見つけることは、コード、部分空間、格子を含むいくつかの文脈で生じる根本的な問題である。 我々は、PCP定理をバイパスする新しいアプローチを用いて、これらの変種すべてに対して強い不適合性を証明した。 我々の主な結果は、任意の定数係数内の実部分空間における最も広いベクトルを近似することがNPハードであることである。
• 参考スコア（独自算出の注目度）: 19.216283072982005
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Finding sparse vectors is a fundamental problem that arises in several contexts including codes, subspaces, and lattices. In this work, we prove strong inapproximability results for all these variants using a novel approach that even bypasses the PCP theorem. Our main result is that it is NP-hard (under randomized reductions) to approximate the sparsest vector in a real subspace within any constant factor; the gap can be further amplified using tensoring. Our reduction has the property that there is a Boolean solution in the completeness case. As a corollary, this immediately recovers the state-of-the-art inapproximability factors for the shortest vector problem (SVP) on lattices. Our proof extends the range of $\ell_p$ (quasi) norms for which hardness was previously known, from $p\geq 1$ to all $p\geq 0$, answering a question raised by [Khot05]. Previous hardness results for SVP, and the related minimum distance problem (MDP) for error-correcting codes, all use lattice/coding gadgets that have an abundance of codewords in a ball of radius smaller than the minimum distance. In contrast, our reduction only needs many codewords in a ball of radius slightly larger than the minimum distance. This enables an easy derandomization of our reduction for finite fields, giving a new elementary proof of deterministic hardness for MDP. We believe this weaker density requirement might offer a promising approach to showing deterministic hardness of SVP, a long elusive goal. The key technical ingredient underlying our result for real subspaces is a proof that in the kernel of a random Rademacher matrix, the support of any two linearly independent vectors have very little overlap. A broader motivation behind this work is the development of inapproximability techniques for problems over the reals. We hope that the approach we develop could enable progress on analytic variants of sparsest vector.
• Abstract（参考訳）: スパースベクトルを見つけることは、コード、部分空間、格子を含むいくつかの文脈で生じる根本的な問題である。 そこで本研究では,PCP定理をバイパスする新しい手法を用いて,これらすべての変種に対して強い不適合性を示す。 我々の主な成果は、任意の定数係数内の実部分空間における最も広いベクトルを近似するNPハード(ランダム化還元の下で)であり、このギャップはテンソル化によってさらに増幅することができる。 我々の還元は、完全性の場合にブール解が存在するという性質を持つ。 結論として、これは格子上の最短ベクトル問題(SVP)に対する最先端の非近似因子を直ちに回復する。 我々の証明は、以前ハードネスが知られていた$\ell_p$ (quasi) ノルムの範囲を、$p\geq 1$ からall $p\geq 0$ まで拡張し、[Khot05] によって提起された質問に答える。 SVPの以前の硬度結果とエラー訂正符号の関連最小距離問題(MDP)はいずれも、最小距離より小さい半径の球にコードワードが豊富に存在する格子/符号化ガジェットを使用している。 対照的に、縮小には最小距離よりわずかに大きい半径の球に多くのコードワードしか必要としない。 これにより、有限体に対する還元の容易なデランドマイズが可能となり、MDPに対する決定論的硬さの新たな初等証明が得られる。 我々は、このより弱い密度要件が、長期の解明目標であるSVPの決定論的硬さを示すための有望なアプローチを提供するかもしれないと信じている。 実部分空間に対する我々の結果の根底にある重要な技術的要素は、ランダムなラデマッハ行列の核において、任意の2つの線型独立ベクトルの支持がほとんど重複していないことの証明である。 この研究の背後にあるより広い動機は、現実上の問題に対する不適応性技術の開発である。 私たちが開発しているアプローチは、最も広いベクトルの分析的変異の進展を可能にすることを願っている。

関連論文リスト

• The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem [53.446980306786095]
  スムースブースターは任意の例にあまり重みを付けない分布を生成する。 もともとは耐雑音性のために導入されたが、そのようなブースターは微分プライバシー、軽度、量子学習理論にも応用されている。
  論文  参考訳（メタデータ） (2024-09-17T23:09:25Z)
• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  我々は,PCAが信号の大きさの臨界値で計算的に困難になることを示す。 我々は、与えられた次数の不変量に対して明示的でほぼ直交的な基底を与える新しい対象の集合を定義する。 また、異なるアンサンブルを区別する新しい問題も分析できます。
  論文  参考訳（メタデータ） (2024-04-29T14:33:24Z)
• Improved Hardness Results for Learning Intersections of Halfspaces [2.1393480341554736]
  不適切な設定でハーフ空間の弱学習交差点に対して、強い(そして驚くほど単純な)下界を示す。 我々は、$omega(log log N)$ halfspaces を$N$で学習しても超多項式時間を要することを示すことで、このギャップを著しく狭めている。 具体的には、次元$N$の任意の$k$ハーフスペースに対して、精度$N-Omega(k)$、指数関数的に多くのクエリが必要であることを示す。
  論文  参考訳（メタデータ） (2024-02-25T05:26:35Z)
• SKI to go Faster: Accelerating Toeplitz Neural Networks via Asymmetric Kernels [69.47358238222586]
  Toeplitz Neural Networks (TNN) は、印象的な結果を持つ最近のシーケンスモデルである。 我々は, O(n) 計算複雑性と O(n) 相対位置エンコーダ (RPE) 多層パーセプトロン (MLP) と減衰バイアスコールの低減を目指す。 双方向モデルの場合、これはスパースと低ランクのToeplitz行列分解を動機付ける。
  論文  参考訳（メタデータ） (2023-05-15T21:25:35Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Minimizing low-rank models of high-order tensors: Hardness, span, tight relaxation, and applications [26.602371644194143]
  この基本テンソル問題は 1 以上のテンソル階数に対して NP-hard であることを示す。 低次ランクの場合、提案された連続的な再構成は低複素度勾配に基づく最適化に有効である。 低密度パリティチェックコードや一般復号パリティチェックコードなど,多くの難題に対する有望な結果を示す。
  論文  参考訳（メタデータ） (2022-10-16T11:53:42Z)
• Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems [0.49495085874952904]
  特に、この仮定の下では、必ずしもハーフスペースではなく、任意のバイナリ仮説を出力する効率的なアルゴリズムは存在しないことを示す。 これは、最悪の格子問題に基づいて、よく分離されたガウス混合を学習する難しさを示す最近の一連の研究から着想を得たものである。
  論文  参考訳（メタデータ） (2022-07-28T11:44:39Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。 我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。 標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
  論文  参考訳（メタデータ） (2021-07-09T16:04:24Z)
• Minimal length in an orbit closure as a semiclassical limit [1.6312226592634047]
  不変理論では、ベクトル v の軌道が原点から分離されることは、ある同次不変量が v 上の 0 でないことを言う。 この最適化への接続により、不変理論における多くの問題に対する効率的なアルゴリズムが導かれた。 局所中心極限定理のフーリエ解析的証明から着想を得た、新しく独立した初等証明を提供する。
  論文  参考訳（メタデータ） (2020-04-30T15:19:07Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。 ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
  論文  参考訳（メタデータ） (2020-04-25T05:45:59Z)

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

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