• Thu, 14 Oct 2021 16:00 Approximate CVP in Time 2^{0.802n} by Moritz Venzin (EPFL)

We show that a constant factor approximation of the shortest and closest lattice vector problem in any norm can be computed in time $2^{0.802\, n}$. This contrasts the $2^n$ (gap)-SETH based lower bound that already applies for some tiny, but constant approximation factor. We achieve this result by reducing to the Euclidean case by means of geometric ideas related to high-dimensional coverings. This is joint work with Fritz Eisenbrand and Thomas Rothvoss respectively.

Note the changed time.

Speaker Bio:

I am a Ph.D. student at Ecole Polytechnique fédérale de Lausanne (EPFL), supervised by Fritz Eisenbrand. My work is mostly on algorithmic questions related to lattice problems and integer programming.

Venue: