Lattice problem: Difference between revisions

Revision as of 20:46, 7 August 2023

Revision as of 06:49, 8 August 2023

Line 39:

===Hardness results===

Goldreich et al. showed that any hardness of SVP implies the same hardness for CVP.<ref>{{cite journal |first=O. |last=Goldreich |title=Approximating shortest lattice vectors is not harder than approximating closest lattice vectors |journal=Inf. Process. Lett. |volume=71 |issue=2 |year=1999 |pages=55–61 |doi=10.1016/S0020-0190(99)00083-6 |display-authors=etal}}</ref> Using [[Probabilistically checkable proof (complexity)|PCP]] tools, [[Sanjeev Arora|Arora]] et al. showed that CVP is hard to approximate within factor <math>2^{\log^{1-\epsilon}(n)}</math> unless <math>\operatorname{NP} \subseteq \operatorname{DTIME}(2^{\operatorname{poly}(\log n)})</math>.<ref>{{cite book |first=Sanjeev |last=Arora |date=1993 |year=1993 |title=Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science |chapter=The hardness of approximate optima in lattices, codes, and systems of linear equations |journal=J. Comput. Syst. Sci. |volume=54 |issue=2 |pages=317–331 |doi=10.1109/SFCS.1993.366815 |display-authors=etal|isbn=978-0-8186-4370-5 |s2cid=44988406 }}</ref> Dinur et al. strengthened this by giving a NP-hardness result with <math>\epsilon=(\log \log n)^c</math> for <math>c<1/2</math>.<ref>{{cite journal |first=I. |last=Dinur |title=Approximating CVP to Within Almost-Polynomial Factors is NP-Hard |journal=Combinatorica |volume=23 |issue=2 |year=2003 |pages=205–243 |doi=10.1007/s00493-003-0019-y |s2cid=45754954 |display-authors=etal}}</ref>

===Sphere decoding===