中間点ヘッセ行列による最短ベクトル問題の$2^{0.6039n}$時間での解法

本論文では、最短ベクトル問題（SVP）に対する確率的アルゴリズムを提案します。n次元格子$\mathcal L$に対して、我々のアルゴリズムは、古典計算で$2^{0.6039n+o(n)}$時間、量子計算で$2^{0.5411n+o(n)}$時間、および空間計算量$2^{0.5n+o(n)}$でSVPを解きます。これは、Aggarwal、Dadush、Regev、およびStephens-Davidowitzによる既存の最良アルゴリズム（$2^{n+o(n)}$時間および空間）を改善するものです。 我々のアルゴリズムは、半最短ベクトルにおける周期ガウス関数のヘッセ行列の性質を強く利用します。最短ベクトル$v \in \mathcal L$に対して、$v/2$におけるヘッセ行列は$v$に近い固有ベクトルを持ち、これを利用して（前処理済みの）有界距離デコーディングアルゴリズムを用いて$v$を復元できます。 格子$\mathcal L$を法とする周期性により、候補となる中間点は$\/2\mathcal L$におけるパリティクラスによってインデックス付けされます。我々のアルゴリズムは、離散ガウスサンプリングを用いて対応するヘッセ行列を推定することにより、最短ベクトルのクラスを探索します。 ランダム格子コセットおよび様々なサンプリング技術を用いてアルゴリズムを最適化し、最終的な計算量を達成します。これらの最適化技術は、独立した興味深いものである可能性があります。