Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
Sampling Methods for Shortest Vectors, Closest Vectors and Successive Minima
verfasst von : Johannes Blömer, Stefanie Naewe
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper we introduce a new lattice problem, the
subspace avoiding problem
(
Sap
). We describe a probabilistic single exponential time algorithm for
Sap
for arbitrary ℓ
p
norms. We also describe polynomial time reductions for four classical problems from the geometry of numbers, the
shortest vector problem
, the
closest vector problem
, the
successive minima problem
, and the
shortest independent vectors problem (
)
to
Sap
, establishing probabilistic single exponential time algorithms for them. The result generalize and extend previous results of Ajtai, Kumar and Sivakumar. The results on
and
are new for all norms. The results on
and
generalize previous results of Ajtai et al. for the ℓ
2
norm to arbitrary ℓ
p
norms.