Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors

Ishay Haviv 1 Oded Regev 2, 1
2 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : We show that unless NP⊆RTIME(2poly(logn)), there is no polynomial-time algorithm approximating the Shortest Vector Problem (SVP) on n-dimensional lattices in the ℓp norm (1≤p<∞) to within a factor of 2(logn)1−ε for any ε>0. This improves the previous best factor of 2(logn)1/2−ε under the same complexity assumption due to Khot (J. ACM, 2005). Under the stronger assumption NP⊈RSUBEXP, we obtain a hardness factor of nc/loglogn for some c>0. Our proof starts with Khot's SVP instances that are hard to approximate to within some constant. To boost the hardness factor we simply apply the standard tensor product of lattices. The main novel part is in the analysis, where we show that the lattices of Khot behave nicely under tensorization. At the heart of the analysis is a certain matrix inequality which was first used in the context of lattices by de Shalit and Parzanchevski.
Type de document :
Article dans une revue
Theory of Computing, University of Chicago, Department of Computer Science, 2012, 8 (1), pp.513-531. 〈10.4086/toc.2012.v008a023〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01111558
Contributeur : Brigitte Briot <>
Soumis le : vendredi 30 janvier 2015 - 15:29:53
Dernière modification le : vendredi 25 mai 2018 - 12:02:05

Lien texte intégral

Identifiants

Collections

Citation

Ishay Haviv, Oded Regev. Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors. Theory of Computing, University of Chicago, Department of Computer Science, 2012, 8 (1), pp.513-531. 〈10.4086/toc.2012.v008a023〉. 〈hal-01111558〉

Partager

Métriques

Consultations de la notice

128