Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
From MaRDI portal
Publication:5494988
DOI10.1109/FOCS.2011.31zbMath1292.68091arXiv1011.5666OpenAlexW1970422301MaRDI QIDQ5494988
Chris Peikert, Daniel Dadush, Santosh Vempala
Publication date: 30 July 2014
Published in: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1011.5666
Analysis of algorithms and problem complexity (68Q25) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Integer programming (90C10) Applications of the theory of convex sets and geometry of numbers (covering radius, etc.) to coding theory (94B75)
Related Items
New algorithms for minimizing the weighted number of tardy jobs on a single machine ⋮ The Integrality Number of an Integer Program ⋮ Covering convex bodies and the closest vector problem ⋮ Voronoi Cells of Lattices with Respect to Arbitrary Norms ⋮ Enumerating Integer Points in Polytopes with Bounded Subdeterminants ⋮ A parameterized view to the robust recoverable base problem of matroids under structural uncertainty ⋮ On lattice point counting in \(\varDelta\)-modular polyhedra ⋮ Approximate CVP in time \(2^{0.802 n}\) -- now in any norm! ⋮ A note on the concrete hardness of the shortest independent vector in lattices ⋮ Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields ⋮ Minimization of even conic functions on the two-dimensional integral lattice ⋮ Minimum-Cost $$b$$-Edge Dominating Sets on Trees ⋮ New transference theorems on lattices possessing \(n^\varepsilon\)-unique shortest vectors ⋮ Integer programming in parameterized complexity: five miniatures ⋮ A polynomial algorithm for minimizing discrete convic functions in fixed dimension ⋮ On the complexity of quasiconvex integer minimization problem ⋮ Block-structured integer programming: can we parameterize without the largest coefficient? ⋮ Enumeration and unimodular equivalence of empty delta-modular simplices ⋮ Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems ⋮ On lattice-based algebraic feedback shift registers synthesis for multisequences ⋮ On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems ⋮ Combinatorial \(n\)-fold integer programming and applications ⋮ The isotropic position and the reverse Santaló inequality ⋮ A randomized sieving algorithm for approximate integer programming ⋮ Approximate CVP_p in Time 2^{0.802 n} ⋮ Algorithms for the Shortest and Closest Lattice Vector Problems ⋮ Integer Programming in Parameterized Complexity: Three Miniatures. ⋮ On the parameterized tractability of single machine scheduling with rejection ⋮ FPT-algorithms for some problems related to integer programming ⋮ Minimum-cost \(b\)-edge dominating sets on trees ⋮ On the rational polytopes with Chvátal rank 1 ⋮ Unnamed Item ⋮ Approximate CVP\(_p\) in time \(2^{0.802n}\) ⋮ Sublinear Root Detection and New Hardness Results for Sparse Polynomials over Finite Fields ⋮ Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting ⋮ Deterministic Construction of an Approximate M-Ellipsoid and its Application to Derandomizing Lattice Algorithms ⋮ Slide reduction, revisited -- filling the gaps in SVP approximation ⋮ The remote set problem on lattices ⋮ The integrality number of an integer program ⋮ Constructing lattice-free gradient polyhedra in dimension two
