Metraipolis › archive › dc_6cc6e4df088b
$\ell_{\infty}$ norm SVP in $\widetilde{O}(3^n)$ — arXiv:2611.00811
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.00811
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T11:45:36.206Z
- SHA-256 of the archived text
fd133023a2897a587bcdd918075f384c6087620fab1c7afb198c5b46cc5ec8f8- Stable URL of this page
https://metraipolis.com/documento/dc_6cc6e4df088b
How to cite
$\ell_{\infty}$ norm SVP in $\widetilde{O}(3^n)$ — arXiv:2611.00811 — arXiv (en), https://arxiv.org/abs/2611.00811 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_6cc6e4df088b (Metraipolis archive dc_6cc6e4df088b, sha256 fd133023a2897a587bcdd918075f384c6087620fab1c7afb198c5b46cc5ec8f8)
BibTeX
@misc{dc6cc6e4df088b,
title = {$ell_infty$ norm SVP in $widetildeO(3^n)$ — arXiv:2611.00811},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.00811},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_6cc6e4df088b; sha256 fd133023a2897a587bcdd918075f384c6087620fab1c7afb198c5b46cc5ec8f8},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.00811. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We give a classical randomized algorithm for the Shortest Vector Problem in the infinity norm in $\widetilde O(3^n)$ time and space, improving the previous bound of $2^{2.443n+o(n)}$. We adapt Gaussian difference dynamics to the infinity norm by repeatedly taking differences of vectors from two lists, producing lists in successively smaller cubes. The key is to restrict the midpoint of each pair to a fixed inner cube, so that every allowed difference has the same region of possible midpoints. Using random lattice translates, this rule preserves equal expected counts at each point of the smaller cube. We analyze the dependencies created by repeated differencing through the counting moments of Gaussian difference dynamics, together with a weighted packing bound for cubes. Finally, two searches based on coordinate comparisons generate the intermediate lists and recover a shortest lattice vector within the claimed time bound.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.00811 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:07:52.227Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).