Algorithms in computer science \{For numerical algorithms, see 65-XX; for combinatorics and graph theory, see 05C85, 68Rxx\}
182 mapped entries · Browse and filter all →
Counts include all statuses and descendants. Classifications are editorial or inferred from community fields, not an AMS assessment of the problem.
Solve CVP on L 1 otimes L 2 efficiently using operatorname poly (n) calls to CVP oracles for the rank- n factors.
In polynomial time, approximate ideal-lattice SVP within operatorname poly (n) over mathbb Z[x]/(x^n+1) for power-of-two n .
Construct a classical reduction operatorname poly ( gamma,n) text -SIVP leq gamma text -GapSIVP .
Construct a dimension-preserving reduction operatorname poly ( gamma,n) text -SVP leq gamma text -SIVP .
Construct a dimension-preserving reduction gamma text -CVP leq Omega( gamma) text -GapCVP .
Approximate rank- n Euclidean shortest vector within 2^ O(n/ log n) in polynomial time.
Find a shortest nonzero vector in polynomial time from an arbitrary basis of a lattice isometric to mathbb Z^n .
Achieve time 2^ cn for rank- n exact Euclidean closest vector, with c<1 classically or c leq1/2 quantumly.
For each p geq1 , solve exact closest vector in ell p on rank- n lattices in time 2^ O(n) .
Solve exact Euclidean closest vector on rank- n lattices in time 2^ O(n) and space n^ O(1) .
These are selected sources for the parent class. Article coverage is a first reviewed selection, and may not cover this exact subcategory.
Springer Nature
Discrete geometry and geometric computation
SIAM
Theory of computation
SIAM
Applied and computational mathematics reviews
2007 · 2 questions extracted
2020 · 0 questions extracted
MSC2020 © Mathematical Reviews (AMS) and zbMATH · CC BY-NC-SA 4.0 · Official PDF, page 178