Deterministic construction of an approximate M-ellipsoid and its applications to derandomizing lattice algorithms

zbMATH Open1421.68209arXiv1107.5478MaRDI QIDQ5743489FDOQ5743489

Authors: Daniel Dadush, Santosh S. Vempala 

Publication date: 10 May 2019

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.

Full work available at URL: https://arxiv.org/abs/1107.5478

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)

Mathematics Subject Classification ID

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)

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
• Robust Stochastic Approximation Approach to Stochastic Programming
• Geometric algorithms and combinatorial optimization
• Entropy and asymptotic geometry of non-symmetric convex bodies
• Title not available (Why is that?)
• Title not available (Why is that?)
• On convex perturbations with a bounded isotropic constant
• Factoring polynomials with rational coefficients
• Integer Programming with a Fixed Number of Variables
• Hit-and-Run from a Corner
• Worst‐Case to Average‐Case Reductions Based on Gaussian Measures
• Distances between non-symmetric convex bodies and the \(MM^*\)-estimate
• Hyperplane projections of the unit ball of \(\ell_{p}^{n}\)
• Inequalities for convex bodies and polar reciprocal lattices in \(\mathbb{R}^ n\)
• Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
• Title not available (Why is that?)
• Title not available (Why is that?)
• Simulated Annealing for Convex Optimization
• Some sieving algorithms for lattice problems
• Title not available (Why is that?)
• Lattice reduction: a toolbox for the cryptoanalyst

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)