Annual Symposium on Foundations of Computer Science

Approximating-CVP to within almost-polynomial factors is NP-hard

Irit Dinur, Guy Kindler, Muli Safra

Published Nov 27, 2002• 56 citations

Abstract

This paper shows the closest vector in a lattice to be NP-hard to approximate to within any factor up to 2/sup (logn)1-4/ where /spl epsiv/=(loglogn)/sup -c/ for any constant c< 1/2.

DOI: 10.1109/sfcs.1998.743433

Related papers

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

Ishay Haviv, Oded Regev

arXiv:1806.04087Theory of ComputingJan 1, 201248 citations

Lattice Algorithms for Multivariate L ∞ Approximation in the Worst-Case Setting

Frances Y. Kuo, G.W. Wasilkowski, Henryk Woźniakowski

Constructive ApproximationSep 23, 200921 citations

The hardness of approximate optima in lattices, codes, and systems of linear equations

Sanjeev Arora, László Babai, Jacques Stern +1 more

Annual Symposium on Foundations of Computer ScienceDec 30, 2002181 citations

Hardness of Approximating the Closest Vector Problem with Pre-Processing

Mikhail Alekhnovich, Subhash Khot, Guy Kindler +1 more

Computational ComplexityDec 1, 201115 citations

Hardness of approximating the minimum distance of a linear code

Ilya I. Dumer, Daniele Micciancio, Madhu Sudan

Annual Symposium on Foundations of Computer ScienceJan 20, 200341 citations

Lattice Rules for Multivariate Approximation in the Worst Case Setting

Frances Y. Kuo, Ian H. Sloan, Henryk Woźniakowski

Springer eBooksFeb 1, 200662 citations

Annual Symposium on Foundations of Computer Science

Approximating-CVP to within almost-polynomial factors is NP-hard

Irit Dinur, Guy Kindler, Muli Safra

Published Nov 27, 2002• 56 citations

Publisher

Abstract

This paper shows the closest vector in a lattice to be NP-hard to approximate to within any factor up to 2/sup (logn)1-4/ where /spl epsiv/=(loglogn)/sup -c/ for any constant c< 1/2.

DOI: 10.1109/sfcs.1998.743433

Related papers

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

Ishay Haviv, Oded Regev

$ \newcommand{\SVP}{\mathsf{SVP}} \newcommand{\NP}{\mathsf{NP}} \newcommand{\RP}{\mathsf{RP}} \newcommand{\RTIME}{\mathsf{RTIME}} \newcommand{\RSUBEXP}{\mathsf{RSUBEXP}} \newcommand{\poly}{\mathop{\mathrm{poly}}} \newcommand{\eps}{\varepsilon} $ We show that unless $\NP \subseteq \RTIME (2^{\poly(\log{n})})$, there is no polynomial-time algorithm approximating the Shortest Vector Problem ($\SVP$) on $n$ -dimensional lattices in the $\ell_p$ norm ( $1 \leq p<\infty$ ) to within a factor of $2^{(\log{n})^{1-\eps}}$ for any $\eps >0$. This improves the previous best factor of $2^{(\log{n})^{1/2-\eps}}$ under the same complexity assumption due to Khot (J. ACM, 2005). Under the stronger assumption $\NP \nsubseteq \RSUBEXP$, we obtain a hardness factor of $n^{c/\log\log{n}}$ 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.$ \newcommand{\SVP}{\mathsf{SVP}} \newcommand{\NP}{\mathsf{NP}} \newcommand{\RP}{\mathsf{RP}} \newcommand{\RTIME}{\mathsf{RTIME}} \newcommand{\RSUBEXP}{\mathsf{RSUBEXP}} \newcommand{\poly}{\mathop{\mathrm{poly}}} \newcommand{\eps}{\varepsilon} $ We show that unless $\NP \subseteq \RTIME (2^{\poly(\log{n})})$, there is no polynomial-time algorithm approximating the Shortest Vector Problem ($\SVP$) on $n$-dimensional lattices in the $\ell_p$ norm ($1 \leq p<\infty$) to within a factor of $2^{(\log{n})^{1-\eps}}$ for any $\eps >0$. This improves the previous best factor of $2^{(\log{n})^{1/2-\eps}}$ under the same complexity assumption due to Khot (J. ACM, 2005). Under the stronger assumption $\NP \nsubseteq \RSUBEXP$, we obtain a hardness factor of $n^{c/\log\log{n}}$ 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.

arXiv:1806.04087Theory of ComputingJan 1, 201248 citations

Lattice Algorithms for Multivariate L ∞ Approximation in the Worst-Case Setting

Frances Y. Kuo, G.W. Wasilkowski, Henryk Woźniakowski

Constructive ApproximationSep 23, 200921 citations

The hardness of approximate optima in lattices, codes, and systems of linear equations

Sanjeev Arora, László Babai, Jacques Stern +1 more

We prove the following about the Nearest Lattice Vector Problem (in any l/sub p/ norm), the Nearest Code-word Problem for binary codes, the problem of learning a halfspace in the presence of errors, and some other problems. 1. Approximating the optimum within any constant factor is NP-hard. 2. If for some /spl epsiv/>0 there exists a polynomial time algorithm that approximates the optimum within a factor of 2/sup log(0.5-/spl epsiv/)/ /sup n/ then NP is in quasi-polynomial deterministic time: NP/spl sube/DTIME(n/sup poly(log/ /sup n)/). Moreover, we show that result 2 also holds for the Shortest Lattice Vector Problem in the l/sub /spl infin// norm. Improving the factor 2/sup log(0.5-/spl epsiv/)/ /sup n/ to /spl radic/(dim) for either of the lattice problems would imply the hardness of the Shortest Vector Problem in l/sub 2/ norm; an old open problem. Our proofs use reductions from few-prover, one-round interactive proof systems, either directly, or through a set-cover problem.>We prove the following about the Nearest Lattice Vector Problem (in any l/sub p/ norm), the Nearest Code-word Problem for binary codes, the problem of learning a halfspace in the presence of errors, and some other problems. 1. Approximating the optimum within any constant factor is NP-hard. 2. If for some /spl epsiv/>0 there exists a polynomial time algorithm that approximates the optimum within a factor of 2/sup log(0.5-/spl epsiv/)/ /sup n/ then NP is in quasi-polynomial deterministic time: NP/spl sube/DTIME(n/sup poly(log/ /sup n)/). Moreover, we show that result 2 also holds for the Shortest Lattice Vector Problem in the l/sub /spl infin// norm. Improving the factor 2/sup log(0.5-/spl epsiv/)/ /sup n/ to /spl radic/(dim) for either of the lattice problems would imply the hardness of the Shortest Vector Problem in l/sub 2/ norm; an old open problem. Our proofs use reductions from few-prover, one-round interactive proof systems, either directly, or through a set-cover problem.>

Annual Symposium on Foundations of Computer ScienceDec 30, 2002181 citations

Hardness of Approximating the Closest Vector Problem with Pre-Processing

Mikhail Alekhnovich, Subhash Khot, Guy Kindler +1 more

Computational ComplexityDec 1, 201115 citations

Hardness of approximating the minimum distance of a linear code

Ilya I. Dumer, Daniele Micciancio, Madhu Sudan

We show that the minimum distance of a linear code (or equivalently, the weight of the lightest codeword) is not approximable to within any constant factor in random polynomial time (RP), unless NP equals RP. Under the stronger assumption that NP is not contained in RQP (random quasi-polynomial time), we show that the minimum distance is not approximable to within the factor 2/sup log(1-/spl epsiv/)n/, for any /spl epsiv/>0, where n denotes the block length of the code. Our results hold for codes over every finite field, including the special case of binary codes. In the process we show that the nearest codeword problem is hard to solve even under the promise that the number of errors is (a constant factor) smaller than the distance of the code. This is a particularly meaningful version of the nearest codeword problem. Our results strengthen (though using stronger assumptions) a previous result of A. Vardy (1997) who showed that the minimum distance is NP-hard to compute exactly. Our results are obtained by adapting proofs of analogous results for integer lattices due to M. Ajtai (1998) and D. Micciancio (1998). A critical component in the adaptation is our use of linear codes that perform better than random (linear) codes.We show that the minimum distance of a linear code (or equivalently, the weight of the lightest codeword) is not approximable to within any constant factor in random polynomial time (RP), unless NP equals RP. Under the stronger assumption that NP is not contained in RQP (random quasi-polynomial time), we show that the minimum distance is not approximable to within the factor 2/sup log(1-/spl epsiv/)n/, for any /spl epsiv/>0, where n denotes the block length of the code. Our results hold for codes over every finite field, including the special case of binary codes. In the process we show that the nearest codeword problem is hard to solve even under the promise that the number of errors is (a constant factor) smaller than the distance of the code. This is a particularly meaningful version of the nearest codeword problem. Our results strengthen (though using stronger assumptions) a previous result of A. Vardy (1997) who showed that the minimum distance is NP-hard to compute exactly. Our results are obtained by adapting proofs of analogous results for integer lattices due to M. Ajtai (1998) and D. Micciancio (1998). A critical component in the adaptation is our use of linear codes that perform better than random (linear) codes.

Annual Symposium on Foundations of Computer ScienceJan 20, 200341 citations

Lattice Rules for Multivariate Approximation in the Worst Case Setting

Frances Y. Kuo, Ian H. Sloan, Henryk Woźniakowski

Springer eBooksFeb 1, 200662 citations

n

-dimensional lattices in the

\ell_p

norm (

1 \leq p<\infty

) to within a factor of $2^{(\log{n})^{1-\eps}}$ for any $\eps >0$. This improves the previous best factor of $2^{(\log{n})^{1/2-\eps}}$ under the same complexity assumption due to Khot (J. ACM, 2005). Under the stronger assumption $\NP \nsubseteq \RSUBEXP$, we obtain a hardness factor of

n^{c/\log\log{n}}

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.