論文の概要: A New Class of Algorithms for Finding Short Vectors in Lattices Lifted from Co-dimension $k$ Codes

• arxiv url: http://arxiv.org/abs/2401.12383v1
• Date: Mon, 22 Jan 2024 22:17:41 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-18 08:27:10.835603
• Title: A New Class of Algorithms for Finding Short Vectors in Lattices Lifted from Co-dimension $k$ Codes
• Title（参考訳）: Co-dimension $k$符号による格子内短ベクトル探索のための新しいアルゴリズム
• Authors: Robert Lin, Peter W. Shor,
• Abstract要約: 共次元$k$ over $mathbbZ_Pd$, ここでは$P$は素数である。 共次元の$$は、プロジェクションのパッキング特性である mod $P$ を1つの双対符号ワードに初期セットの非格子ベクトルに利用することで解決される。 そこで本研究では,反復数,すなわち全長拡大係数を最小化して,短い格子ベクトルが得られることを示す。
• 参考スコア（独自算出の注目度）: 1.8416014644193066
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We introduce a new class of algorithms for finding a short vector in lattices defined by codes of co-dimension $k$ over $\mathbb{Z}_P^d$, where $P$ is prime. The co-dimension $1$ case is solved by exploiting the packing properties of the projections mod $P$ of an initial set of non-lattice vectors onto a single dual codeword. The technical tools we introduce are sorting of the projections followed by single-step pairwise Euclidean reduction of the projections, resulting in monotonic convergence of the positive-valued projections to zero. The length of vectors grows by a geometric factor each iteration. For fixed $P$ and $d$, and large enough user-defined input sets, we show that it is possible to minimize the number of iterations, and thus the overall length expansion factor, to obtain a short lattice vector. Thus we obtain a novel approach for controlling the output length, which resolves an open problem posed by Noah Stephens-Davidowitz (the possibility of an approximation scheme for the shortest-vector problem (SVP) which does not reduce to near-exact SVP). In our approach, one may obtain short vectors even when the lattice dimension is quite large, e.g., 8000. For fixed $P$, the algorithm yields shorter vectors for larger $d$. We additionally present a number of extensions and generalizations of our fundamental co-dimension $1$ method. These include a method for obtaining many different lattice vectors by multiplying the dual codeword by an integer and then modding by $P$; a co-dimension $k$ generalization; a large input set generalization; and finally, a "block" generalization, which involves the replacement of pairwise (Euclidean) reduction by a $k$-party (non-Euclidean) reduction. The $k$-block generalization of our algorithm constitutes a class of polynomial-time algorithms indexed by $k\geq 2$, which yield successively improved approximations for the short vector problem.
• Abstract（参考訳）: 共次元$k$ over $\mathbb{Z}_P^d$, ここでは$P$は素数である。 共次元の$$は、プロジェクションのパッキング特性である mod $P$ を1つの双対符号ワードに初期セットの非格子ベクトルに利用することで解決される。 私たちが導入した技術ツールは射影のソートであり、続いて単段階のユークリッド対射影の減少が続き、正の値の射影の単調収束が 0 となる。 ベクトルの長さは、反復ごとに幾何学的因子によって成長する。 固定された$P$と$d$と、十分なユーザ定義の入力セットに対して、反復回数を最小化し、したがって全体の長さ拡大係数を最小化し、短い格子ベクトルを得ることができることを示す。 そこで我々は,Noah Stephens-Davidowitz による開問題(最短ベクトル問題 (SVP) に対する近似スキームの可能性)を解いた出力長を制御する新しい手法を得る。 このアプローチでは、格子次元が非常に大きい場合、例えば、8000 である場合でも、短いベクトルを得ることができる。 固定$P$の場合、このアルゴリズムはより大きい$d$に対してより短いベクトルを生成する。 さらに、基本共次元法の多くの拡張と一般化を提示する。 これには整数で二重コードワードを乗算し、$P$で修飾することで、多くの異なる格子ベクトルを得る方法、共同次元の$k$一般化、大きな入力集合の一般化、そして最後に、$k$パーティー(非ユークリッド)還元による対(ユークリッド)還元を置き換える「ブロック」一般化が含まれる。 我々のアルゴリズムの$k$-block一般化は、$k\geq 2$でインデックス付けされた多項式時間アルゴリズムのクラスを構成する。

関連論文リスト

• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Projection-Free Online Convex Optimization via Efficient Newton Iterations [10.492474737007722]
  本稿では、凸領域$mathcalKサブセットmathbbRd$に対するオンライン凸最適化(OCO)のための新しいプロジェクションフリーアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-19T18:48:53Z)
• Orthogonal Directions Constrained Gradient Method: from non-linear equality constraints to Stiefel manifold [16.099883128428054]
  直交方向制約法(ODCGM)という新しいアルゴリズムを提案する。 ODCGMはベクトル空間へのプロジェクションのみを必要とする。 以上より, ODCGMは, ほぼ最適のオラクル複合体を呈することを示した。
  論文  参考訳（メタデータ） (2023-03-16T12:25:53Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Halpern-Type Accelerated and Splitting Algorithms For Monotone Inclusions [14.445131747570962]
  我々は、最大単調方程式のクラスを解くために、新しいタイプの加速アルゴリズムを開発する。 我々の手法は[32]におけるハルパーン型固定点反復と呼ばれるものに依存しており、近年多くの研究者が利用している。
  論文  参考訳（メタデータ） (2021-10-15T15:26:32Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• FANOK: Knockoffs in Linear Time [73.5154025911318]
  本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。 当社のメソッドは、最大50,000ドルという問題でテストしています。
  論文  参考訳（メタデータ） (2020-06-15T21:55:34Z)
• Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing [22.337756118270217]
  基本統計量に対する2つの方法を開発した:$epsilon$-corrupted set of $n$ sample from a $d$-linear sub-Gaussian distribution。 最初のロバストなアルゴリズムは反復フィルタリングを時間内に実行し、近似固有ベクトルを返し、単純なフィルタリングアプローチに基づいている。 私たちの2つめは、わずかに悪い近似係数を達成し、軽度のスペクトルギャップ仮定の下でほぼ自明な時間とイテレーションで実行します。
  論文  参考訳（メタデータ） (2020-06-12T07:45:38Z)
• Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity [63.29100726064574]
  有限格子上の半空間に対して微分プライベート学習器を$mathbbRd$で$G$で、サンプル複雑性を$approx d2.5cdot 2log*|G|$で表す。 学習者のためのビルディングブロックは、線形実現可能性問題を解くために、微分プライベートな新しいアルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-16T16:12:10Z)

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

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