Deterministic construction of an approximate M-ellipsoid and its applications to derandomizing lattice algorithms
From MaRDI portal
(Redirected from Publication:5743489)
Lattices and convex bodies (number-theoretic aspects) (11H06) Number-theoretic algorithms; complexity (11Y16) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Approximation algorithms (68W25)
Abstract: We give a deterministic O(log n)^n algorithm for the {em Shortest Vector Problem (SVP)} of a lattice under {em any} norm, improving on the previous best deterministic bound of n^O(n) for general norms and nearly matching the bound of 2^O(n) for the standard Euclidean norm established by Micciancio and Voulgaris (STOC 2010). Our algorithm can be viewed as a derandomization of the AKS randomized sieve algorithm, which can be used to solve SVP for any norm in 2^O(n) time with high probability. We use the technique of covering a convex body by ellipsoids, as introduced for lattice problems in (Dadush et al., FOCS 2011). Our main contribution is a deterministic approximation of an M-ellipsoid of any convex body. We achieve this via a convex programming formulation of the optimal ellipsoid with the objective function being an n-dimensional integral that we show can be approximated deterministically, a technique that appears to be of independent interest.
Recommendations
- Near-optimal deterministic algorithms for volume computation via M-ellipsoids
- A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
- Approximate CVP in time \(2^{0.802 n}\) -- now in any norm!
- A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
- Solving the shortest vector problem in 2ⁿ time using discrete Gaussian sampling (extended abstract)
Cites work
- A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
- A sieve algorithm for the shortest lattice vector problem
- A Stochastic Approximation Method
- Distances between non-symmetric convex bodies and the \(MM^*\)-estimate
- Entropy and asymptotic geometry of non-symmetric convex bodies
- Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
- Factoring polynomials with rational coefficients
- Geometric algorithms and combinatorial optimization
- Hit-and-Run from a Corner
- scientific article; zbMATH DE number 1574599 (Why is no real title available?)
- scientific article; zbMATH DE number 4213909 (Why is no real title available?)
- scientific article; zbMATH DE number 3975773 (Why is no real title available?)
- scientific article; zbMATH DE number 194093 (Why is no real title available?)
- scientific article; zbMATH DE number 1852142 (Why is no real title available?)
- Hyperplane projections of the unit ball of \(\ell_{p}^{n}\)
- Inequalities for convex bodies and polar reciprocal lattices in \(\mathbb{R}^ n\)
- Integer Programming with a Fixed Number of Variables
- Lattice reduction: a toolbox for the cryptoanalyst
- On convex perturbations with a bounded isotropic constant
- Robust Stochastic Approximation Approach to Stochastic Programming
- Simulated Annealing for Convex Optimization
- Some sieving algorithms for lattice problems
- Worst‐Case to Average‐Case Reductions Based on Gaussian Measures
Cited in
(5)- Minimum-cost b-edge dominating sets on trees
- A parameterized view to the robust recoverable base problem of matroids under structural uncertainty
- Minimum-cost \(b\)-edge dominating sets on trees
- Voronoi cells of lattices with respect to arbitrary norms
- Near-optimal deterministic algorithms for volume computation via M-ellipsoids
This page was built for publication: Deterministic construction of an approximate M-ellipsoid and its applications to derandomizing lattice algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5743489)
