A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations
From MaRDI portal
Publication:2848225
DOI10.1137/100811970zbMath1275.68079OpenAlexW2133465710MaRDI QIDQ2848225
Panagiotis Voulgaris, Daniele Micciancio
Publication date: 25 September 2013
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/100811970
Analysis of algorithms and problem complexity (68Q25) Lattices and convex bodies (number-theoretic aspects) (11H06)
Related Items (30)
Voronoi Cells of Lattices with Respect to Arbitrary Norms ⋮ The parameterized complexity of geometric graph isomorphism ⋮ Scalable revocable identity-based signature over lattices in the standard model ⋮ Minimization of even conic functions on the two-dimensional integral lattice ⋮ Lifts for Voronoi cells of lattices ⋮ Complexity of optimizing over the integers ⋮ Faster integer multiplication using short lattice vectors ⋮ Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems ⋮ On fluxes in the \(1^9\) Landau-Ginzburg model ⋮ Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP) ⋮ The Reductions for the Approximating Covering Radius Problem ⋮ A randomized sieving algorithm for approximate integer programming ⋮ Generalizing CGAL Periodic Delaunay Triangulations ⋮ A Polynomial Time Algorithm for Solving the Closest Vector Problem in Zonotopal Lattices ⋮ Lattice preconditioning for the real relaxation branch-and-bound approach for integer least squares problems ⋮ On the Bit Security of Elliptic Curve Diffie–Hellman ⋮ An algebraic perspective on integer sparse recovery ⋮ Unnamed Item ⋮ Locally optimal 2-periodic sphere packings ⋮ Noisy polynomial interpolation modulo prime powers ⋮ On compact representations of Voronoi cells of lattices ⋮ Применение теории решеток к анализу схем цифровой подписи ⋮ The randomized slicer for CVPP: sharper, faster, smaller, batchier ⋮ A \(2^{n/2}\)-time algorithm for \(\sqrt{n} \)-SVP and \(\sqrt{n} \)-Hermite SVP, and an improved time-approximation tradeoff for (H)SVP ⋮ A time-distance trade-off for GDD with preprocessing: instantiating the DLW heuristic ⋮ Interpolation and Approximation of Polynomials in Finite Fields over a Short Interval from Noisy Values ⋮ Slide reduction, revisited -- filling the gaps in SVP approximation ⋮ Cryptanalysis of Cramer-Shoup Like Cryptosystems Based on Index Exchangeable Family ⋮ The remote set problem on lattices ⋮ Subexponential class group and unit group computation in large degree number fields
This page was built for publication: A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations
