論文の概要: Inapproximability of Sparsest Vector in a Real Subspace

• arxiv url: http://arxiv.org/abs/2410.02636v2
• Date: Sun, 27 Oct 2024 07:27:33 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-04 01:52:35.900645
• Title: Inapproximability of Sparsest Vector in a Real Subspace
• Title（参考訳）: 実空間におけるスペーサーベクトルの非近似性
• Authors: Vijay Bhattiprolu, Euiwoong Lee,
• Abstract要約: 我々は、実部分空間において最も狭い非零ベクトルを見つけるための強い不近似性を確立する。 任意の定数係数内の部分空間における最も遠いベクトルを近似することはNP-Hardであることが示される。
• 参考スコア（独自算出の注目度）: 1.9943009191774073
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We establish strong inapproximability for finding the sparsest nonzero vector in a real subspace. We show that it is NP-Hard (under randomized reductions) to approximate the sparsest vector in a subspace within any constant factor (or almost polynomial factors in quasipolynomial time). We recover as a corollary state of the art inapproximability for the shortest vector problem (SVP), a foundational problem in lattice based cryptography. Our proof is surprisingly simple, bypassing even the PCP theorem. We are inspired by the homogenization framework from the inapproximability theory of minimum distance problems (MDC) in integer lattices and error correcting codes. We use a combination of (a) \emph{product testing via tensor codes} and (b) \emph{encoding an assignment as a coset of a random code in higher dimensional space} in order to embed non-homogeneous quadratic equations into the sparsest vector problem. (a) is inspired by Austrin and Khot's simplified proof of hardness of MDC over finite fields, and (b) is inspired by Micciancio's semi-derandomization of hardness of SVP. Our reduction involves the challenge of performing (a) over the reals. We prove that tensoring of the kernel of a +1/-1 random matrix furnishes an adequate product test (while still allowing (b)). The proof exposes a connection to Littlewood-Offord theory and relies on a powerful anticoncentration result of Rudelson and Vershynin. Our main motivation in this work is the development of inapproximability theory for problems over the reals. Analytic variants of sparsest vector have connections to small set expansion, quantum separability and polynomial maximization over convex sets, all of which cause similar barriers to inapproximability. The approach we develop could lead to progress on the hardness of some of these problems.
• Abstract（参考訳）: 我々は、実部分空間において最も狭い非零ベクトルを見つけるための強い不近似性を確立する。 我々は、任意の定数係数(あるいは準多項式時間におけるほぼ多項式因子)内の部分空間における最も広いベクトルを近似することは、NP-Hard(ランダム化還元の下で)であることが示される。 我々は,格子型暗号の基本問題である最短ベクトル問題(SVP)に対して,最先端の非近似状態として回復する。 私たちの証明は驚くほど単純で、PCPの定理さえ無視する。 我々は、整数格子および誤り訂正符号における最小距離問題(MDC)の不近似性理論からホモジェナイゼーションフレームワークに着想を得た。 組み合わせて使う (a)テンソルコードによるemph{product testingと (b)非同次二次方程式をスパースベクトル問題に埋め込むために、高次元空間における乱符号の余集合としての代入をエンコードする。 a) は、Ausstrin と Khot の有限体上の MDC の硬さの単純証明に着想を得たものである。 b) は、ミキアシオのSVPの硬さの半デランドマイゼーションに着想を得たものである。 我々の削減にはパフォーマンスの課題が伴う (a) over the reals. +1/-1ランダム行列の核のテンソル化が適切な積テストをもたらすことを証明している(なお許す)。 (b)。 この証明はリトルウッド=オフォード理論との関係を明らかにし、ルデルソンとヴェルシニンの強力な反集中の結果に依存する。 この研究の主な動機は、実数上の問題に対する不適応性理論の開発である。 解析的ベクトルの変種は、小さな集合の展開、量子分離性、凸集合上の多項式の最大化につながり、これら全てが同様の障壁を不適応性に導く。 私たちが開発するアプローチは、これらの問題の一部の難しさを前進させる可能性がある。

関連論文リスト

• 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)

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

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