Dual vectors and lower bounds for the nearest lattice point problem
Let \(L\) be a lattice in \(\mathbb R^ n\) and let \(L^*\) be its dual. The author shows that for each \(x\in\mathbb R^ n\setminus L\) there exists a nonzero \(v\in L^*\) such that \[ \frac{| \{(x,v)\}|}{\| v\|}\geq c_ n\cdot d(x,L), \] where \((x,v)\) is the usual inner product on \(\mathbb R^ n,\) \(\{\alpha\}\) the minimal distance of \(\alpha\) to an integer, \(d(x,L)\) is the distance from \(x\) to \(L\) and \(c_ n\geq (6n^ 2+1)^{-1}.\) The proof is not constructible. The best known constructible proof gives a value \(c_ n\geq 9^{-n}.\)
- Factoring polynomials with rational coefficients
- scientific article; zbMATH DE number 3333393 (Why is no real title available?)
- scientific article; zbMATH DE number 3046578 (Why is no real title available?)
- Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
- Minkowski's Convex Body Theorem and Integer Programming
- On Lovász' lattice reduction and the nearest lattice point problem
- A best lower bound for good lattice points
- Simultaneously good bases of a lattice and its reciprocal lattice
- 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 relation of primal--dual lattices and the complexity of shortest lattice vector problem
- New bounds in some transference theorems in the geometry of numbers
- Inequalities for convex bodies and polar reciprocal lattices in \(\mathbb{R}^ n\)
- On the limits of nonapproximability of lattice problems
- Efficient computation of dual space and directional multiplicity of an isolated point
- The closest vector problem in tensored root lattices of type A and in their duals
- A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor
- Stable and well-rounded lattices in diagonal orbits
- More on average case vs approximation complexity
- Structure versus hardness through the obfuscation lens
- A uniform stability principle for dual lattices
- A DUAL ALGORITHM FOR FINDING A NEAREST PAIR OF POINTS IN TWO POLYTOPES
- Does the dual-sieve attack on learning with errors even work?
- Accurate score prediction for Dual-Sieve attacks
- Nearest lattice point algorithms on semi k-reduced basis
This page was built for publication: Dual vectors and lower bounds for the nearest lattice point problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1107568)
