Faster SVP in Polynomial Space
En palabras de los autores
Kannan's algorithm, as analyzed by Hanrot and Stehl\'e in 2007, solves the exact Euclidean shortest vector problem in polynomial space and time. In the classical setting with polynomial space, we obtain the first improvement on this bound via a randomized algorithm that runs in time. The main idea is to represent a fixed shortest vector in many ways as a difference of samples, thereby enabling the low-space collision search of Lyu and Zhu (SODA 2023) to replace exhaustive enumeration in the original analysis.
Resultado principalEl resumen no menciona limitaciones.
Apareció: lunes, 21 de septiembre. arXiv. Preprint, todavía sin revisión por pares.