On the Shortest Lattice Vector vs. the Shortest Basis

Yael Eisenberg, Itamar Rot, Muli Safra

Given an arbitrary basis for a mathematical lattice, to find a ``good" basis for it is one of the classic and important algorithmic problems. In this note, we give a new and simple…