10 entries matching the current filters. Sorted by recently added.
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) .