Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
From MaRDI portal
Publication:757465
DOI10.1007/BF02128669zbMath0723.11029OpenAlexW1973270757MaRDI QIDQ757465
Claus Peter Schnorr, Jeffrey C. Lagarias, Hendrik W. jun. Lenstra
Publication date: 1990
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02128669
Analysis of algorithms and problem complexity (68Q25) Lattices and convex bodies (number-theoretic aspects) (11H06) Quadratic forms (reduction theory, extreme forms, etc.) (11H55) Minima of forms (11H50)
Related Items
Tight bounds on discrete quantitative Helly numbers, Towards faster polynomial-time lattice reduction, The inapproximability of lattice and coding problems with preprocessing, Generalized degree and optimal Loewner-type inequalities, Lattice basis reduction: Improved practical algorithms and solving subset sum problems, A uniform stability principle for dual lattices, Inequalities for convex bodies and polar reciprocal lattices in \(\mathbb{R}^ n\), Successive minima, intrinsic volumes, and lattice determinants, A hierarchy of polynomial time lattice basis reduction algorithms, The hardness of approximate optima in lattices, codes, and systems of linear equations, Dual vectors and lower bounds for the nearest lattice point problem, Hermitian vector bundles and extension groups on arithmetic schemes. I: Geometry of numbers, Covering sets for plane lattices, Simultaneously good bases of a lattice and its reciprocal lattice, Area-diameter and area-width relations for covering plane sets, Sharper bounds on four lattice constants, New transference theorems on lattices possessing \(n^\varepsilon\)-unique shortest vectors, A polynomial algorithm for minimizing discrete convic functions in fixed dimension, Enumeration and unimodular equivalence of empty delta-modular simplices, Block Reduced Lattice Bases and Successive Minima, Sieving for closest lattice vectors (with preprocessing), More on average case vs approximation complexity, Hardness of approximating the closest vector problem with pre-processing, Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions, Explicit Hard Instances of the Shortest Vector Problem, A randomized sieving algorithm for approximate integer programming, Structure Versus Hardness Through the Obfuscation Lens, On the number of integer points in a multidimensional domain, Lattice Reformulation Cuts, Centerpoints: A Link between Optimization and Convex Geometry, Non-standard approaches to integer programming, La réduction des réseaux. Autour de l'algorithme de Lenstra, Lenstra, Lovász, Reduction of Smith normal form transformation matrices, Improved Rounding for Spline Coefficients and Knots, Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms, Nonembeddability theorems via Fourier analysis, Short Bases of Lattices over Number Fields, Euclidean lattices, theta invariants, and thermodynamic formalism, Hermite’s Constant and Lattice Algorithms, Lamination and antilamination of Euclidean lattices, Hyperelliptic surfaces are Loewner, Multidimensional Extremal Logan’s and Bohman’s Problems, An upper bound on the number of perfect quadratic forms, A relation of primal--dual lattices and the complexity of shortest lattice vector problem, On the limits of nonapproximability of lattice problems, A Polyhedral Frobenius Theorem with Applications to Integer Optimization, Discrete analogues of John's theorem, Analysis of PSLQ, an integer relation finding algorithm, A note on the non-NP-hardness of approximate lattice problems under general Cook reductions., The Restricted Isometry Property of Subsampled Fourier Matrices, A lattice-based public-key cryptosystem, Simultaneous reduction of a lattice basis and its reciprocal basis, Lattice inequalities for convex bodies and arbitrary lattices, On successive minima and intrinsic volumes, A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor, Counting ideals in ray classes, SLIDE REDUCTION, SUCCESSIVE MINIMA AND SEVERAL APPLICATIONS, New bounds in some transference theorems in the geometry of numbers, Approximating the densest sublattice from Rankin’s inequality
Cites Work
- Die Reduktionstheorie der positiven quadratischen Formen
- On Lovász' lattice reduction and the nearest lattice point problem
- A hierarchy of polynomial time lattice basis reduction algorithms
- Factoring polynomials with rational coefficients
- Integer Programming with a Fixed Number of Variables
- Minkowski's Convex Body Theorem and Integer Programming
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
