Deterministic Construction of an Approximate M-Ellipsoid and its Application to Derandomizing Lattice Algorithms

zbMath1421.68209arXiv1107.5478MaRDI QIDQ5743489

Daniel Dadush, Santosh Vempala

Publication date: 10 May 2019

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Number-theoretic algorithms; complexity (11Y16) Lattices and convex bodies (number-theoretic aspects) (11H06) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items

Voronoi Cells of Lattices with Respect to Arbitrary Norms ⋮ A parameterized view to the robust recoverable base problem of matroids under structural uncertainty ⋮ Minimum-Cost $$b$$-Edge Dominating Sets on Trees ⋮ Minimum-cost \(b\)-edge dominating sets on trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On convex perturbations with a bounded isotropic constant
• Factoring polynomials with rational coefficients
• Geometric algorithms and combinatorial optimization
• Lattice reduction: a toolbox for the cryptoanalyst
• Inequalities for convex bodies and polar reciprocal lattices in \(\mathbb{R}^ n\)
• Entropy and asymptotic geometry of non-symmetric convex bodies
• Hyperplane projections of the unit ball of \(\ell_{p}^{n}\)
• Distances between non-symmetric convex bodies and the \(MM^*\)-estimate
• A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations
• Integer Programming with a Fixed Number of Variables
• Some Sieving Algorithms for Lattice Problems
• Robust Stochastic Approximation Approach to Stochastic Programming
• A sieve algorithm for the shortest lattice vector problem
• Simulated Annealing for Convex Optimization
• Worst‐Case to Average‐Case Reductions Based on Gaussian Measures
• Hit-and-Run from a Corner
• Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
• A Stochastic Approximation Method