Deterministic construction of an approximate M-ellipsoid and its applications to derandomizing lattice algorithms
From MaRDI portal
Publication:5743489
Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Approximation algorithms (68W25) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Lattices and convex bodies (number-theoretic aspects) (11H06) Number-theoretic algorithms; complexity (11Y16)
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^n\) time using discrete Gaussian sampling (extended abstract)
Cites work
- 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?)
- A Stochastic Approximation Method
- A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
- A sieve algorithm for the shortest lattice vector problem
- 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
- 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
- Minimum-cost \(b\)-edge dominating sets on trees
- Voronoi cells of lattices with respect to arbitrary norms
- A parameterized view to the robust recoverable base problem of matroids under structural uncertainty
- 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)
