Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
From MaRDI portal
Publication:757465
DOI10.1007/BF02128669zbMATH Open0723.11029OpenAlexW1973270757MaRDI QIDQ757465FDOQ757465
Claus Peter Schnorr, Jeffrey C. Lagarias, H. 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
Recommendations
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)
Cites Work
- 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- On Lovász' lattice reduction and the nearest lattice point problem
- Die Reduktionstheorie der positiven quadratischen Formen
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (67)
- New transference theorems on lattices possessing \(n^\varepsilon\)-unique shortest vectors
- The Generalized Basis Reduction Algorithm
- Non-standard approaches to integer programming
- Nonembeddability theorems via Fourier analysis
- Discrete analogues of John's theorem
- Title not available (Why is that?)
- Slide reduction, successive minima and several~applications
- Analysis of PSLQ, an integer relation finding algorithm
- Lattice Reformulation Cuts
- Sieving for closest lattice vectors (with preprocessing)
- Approximating the densest sublattice from Rankin's inequality
- Inequalities for convex bodies and polar reciprocal lattices in \(\mathbb{R}^ n\)
- Lamination and antilamination of Euclidean lattices
- Simultaneous reduction of a lattice basis and its reciprocal basis
- A relation of primal--dual lattices and the complexity of shortest lattice vector problem
- La réduction des réseaux. Autour de l'algorithme de Lenstra, Lenstra, Lovász
- A Polyhedral Frobenius Theorem with Applications to Integer Optimization
- Lattice basis reduction: Improved practical algorithms and solving subset sum problems
- Hardness of approximating the closest vector problem with pre-processing
- More on average case vs approximation complexity
- Structure Versus Hardness Through the Obfuscation Lens
- A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor
- Euclidean lattices, theta invariants, and thermodynamic formalism
- Simultaneously good bases of a lattice and its reciprocal lattice
- Covering sets for plane lattices
- Dual vectors and lower bounds for the nearest lattice point problem
- Multidimensional Extremal Logan’s and Bohman’s Problems
- Hermitian vector bundles and extension groups on arithmetic schemes. I: Geometry of numbers
- Area-diameter and area-width relations for covering plane sets
- New bounds in some transference theorems in the geometry of numbers
- Reduction of Smith normal form transformation matrices
- Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms
- Short Bases of Lattices over Number Fields
- Lattice inequalities for convex bodies and arbitrary lattices
- Tight bounds on discrete quantitative Helly numbers
- On the limits of nonapproximability of lattice problems
- Counting ideals in ray classes
- Generalized degree and optimal Loewner-type inequalities
- The inapproximability of lattice and coding problems with preprocessing
- Hermite’s Constant and Lattice Algorithms
- Explicit Hard Instances of the Shortest Vector Problem
- On successive minima and intrinsic volumes
- Sur un problème de dualité lié aux sphères en géométrie des nombres. (On a duality problem related to spheres in geometry of numbers)
- A randomized sieving algorithm for approximate integer programming
- Centerpoints: A Link between Optimization and Convex Geometry
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- Improved Rounding for Spline Coefficients and Knots
- Successive minima, intrinsic volumes, and lattice determinants
- On the number of integer points in a multidimensional domain
- Towards faster polynomial-time lattice reduction
- Block Reduced Lattice Bases and Successive Minima
- An upper bound on the number of perfect quadratic forms
- A polynomial algorithm for minimizing discrete convic functions in fixed dimension
- A hierarchy of polynomial time lattice basis reduction algorithms
- Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions
- Hyperelliptic surfaces are Loewner
- A lattice-based public-key cryptosystem
- The Restricted Isometry Property of Subsampled Fourier Matrices
- Title not available (Why is that?)
- A note on the non-NP-hardness of approximate lattice problems under general Cook reductions.
- On polynomial modular number systems over \(\mathbb{Z}/p\mathbb{Z}\)
- A new bound for the orthogonality defect of HKZ reduced lattices
- Linear dependence among Hecke eigenvalues
- Sharper bounds on four lattice constants
- On the smallest ratio problem of lattice bases
- A uniform stability principle for dual lattices
- Enumeration and unimodular equivalence of empty delta-modular simplices
This page was built for publication: Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q757465)
