On the lattice distortion problem

DOI10.4230/LIPICS.ESA.2016.9zbMATH Open1397.68089arXiv1605.03613OpenAlexW2963702407MaRDI QIDQ4606278FDOQ4606278

Authors: Huck Bennett, Daniel Dadush, Noah Stephens-Davidowitz 

Publication date: 2 March 2018

Abstract: We introduce and study the emph{Lattice Distortion Problem} (LDP). LDP asks how "similar" two lattices are. I.e., what is the minimal distortion of a linear bijection between the two lattices? LDP generalizes the Lattice Isomorphism Problem (the lattice analogue of Graph Isomorphism), which simply asks whether the minimal distortion is one. As our first contribution, we show that the distortion between any two lattices is approximated up to a $n^{O(logn)}$ factor by a simple function of their successive minima. Our methods are constructive, allowing us to compute low-distortion mappings that are within a $2^{O(nloglogn/logn)}$ factor of optimal in polynomial time and within a $n^{O(logn)}$ factor of optimal in singly exponential time. Our algorithms rely on a notion of basis reduction introduced by Seysen (Combinatorica 1993), which we show is intimately related to lattice distortion. Lastly, we show that LDP is NP-hard to approximate to within any constant factor (under randomized reductions), by a reduction from the Shortest Vector Problem.

Full work available at URL: https://arxiv.org/abs/1605.03613

Recommendations

• On the lattice isomorphism problem
• scientific article; zbMATH DE number 1256724
• The shortest vector in a lattice is hard to approximate to within some constant
• Lattice problems and norm embeddings
• Lattice problems in NP ∩ coNP

zbMATH Keywords

latticesgeometry of numbersbasis reductionlattice distortionlattice isomoprhism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Lattices and convex bodies (number-theoretic aspects) (11H06)

Cited In (2)

• On lattice dicing
• On the lattice isomorphism problem

This page was built for publication: On the lattice distortion problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606278)