(Gap/S)ETH hardness of SVP
(Gap/S)ETH hardness of SVP
复制标题
(Gap/S)SVP的ETH硬度
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Noah Stephens
中科院分区：
文献类型：
--
作者：
Divesh Aggarwal;Noah Stephens
我们证明了以下定量的硬度结果的最短向量问题的最短向量范数（SVP_p），其中n是输入格的秩。对于“几乎所有”p > p0 ≤ 2.1397，对于某些显式（易于计算）常数Cp > 0，不存在SVP_p的2n/Cp-时间算法，除非（随机化）强指数时间假设（SETH）为假。(E.g.,对于p ≥ 3，Cp < 1 +（p+3）2−p + 10 p2 2− 2 p。对于任意1 ≤ p ≤ ∞，不存在求解SVP_p的2 o（n）-时间算法，除非非均匀间隙-指数时间假设（Gap-ETH）为假。此外，对于每个这样的p，存在一个常数γp > 1，使得即使对于γ p-近似SVP_p，相同的结果也成立。对于p > 2，上述陈述在随机化Gap-ETH的较弱假设下成立。即，除非随机化Gap-ETH为假，否则不存在γ p-近似SVP_p的2 o（n）时间算法。参见http://arxiv.org/abs/1712.00942以获得完整的说明。
We prove the following quantitative hardness results for the Shortest Vector Problem in the ℓp norm (SVP_p), where n is the rank of the input lattice. For “almost all” p > p0 ≈ 2.1397, there is no 2n/Cp-time algorithm for SVP_p for some explicit (easily computable) constant Cp > 0 unless the (randomized) Strong Exponential Time Hypothesis (SETH) is false. (E.g., for p ≥ 3, Cp < 1 + (p+3) 2−p + 10 p2 2−2p.) For any 1 ≤ p ≤ ∞, there is no 2o(n)-time algorithm for SVP_p unless the non-uniform Gap-Exponential Time Hypothesis (Gap-ETH) is false. Furthermore, for each such p, there exists a constant γp > 1 such that the same result holds even for γp-approximate SVP_p. For p > 2, the above statement holds under the weaker assumption of randomized Gap-ETH. I.e., there is no 2o(n)-time algorithm for γp-approximate SVP_p unless randomized Gap-ETH is false. See http://arxiv.org/abs/1712.00942 for a complete exposition.