2026-08-21T18:34:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27448 2026-08-21T14:42:40Z ddc:004 open_access

On the Complexity of Locally Dense Lattices Hirahara, Shuichi Ogitsuka, Kazuki Lattice problems Locally dense lattices Locally dense lattices are central gadgets used to prove the hardness of the Shortest Vector Problem and related lattice problems. Informally, a locally dense lattice is a lattice ℒ that contains exponentially many lattice vectors inside some 𝓁_p ball centered at 𝐬 with radius at most an α < 1 fraction of the length of its shortest nonzero lattice vector. In this paper, taking a "meta" viewpoint on locally dense lattices, we introduce the Locally Dense Lattice Problem (LDLP), the decision problem of determining whether a given input specifies a locally dense lattice. Our main result is that LDLP in 𝓁_p norms for all finite p ≥ log₂ 3 and for the infinity norm is complete for the second level of the polynomial hierarchy. We also compare two standard definitions of local density that appear in prior work. Micciancio’s original definition (FOCS 1998 and SICOMP 2001) uses integer coefficient vectors, while later work by Micciancio (ToC 2012) and by Bennett and Peikert (RANDOM 2023) uses short vectors in a shifted coset. We show that the corresponding promise problems are mutually reducible in deterministic polynomial time, which shows that the two formulations are robust. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shuichi Hirahara and Kazuki Ogitsuka 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.66 urn:nbn:de:0030-drops-274485 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.66 eng https://creativecommons.org/licenses/by/4.0/legalcode