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 (59)
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
This page was built for publication: Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
