Kissing numbers and transference theorems from generalized tail bounds

DOI10.1137/18M1210186MaRDI QIDQ5232155zbMATHOpenAlexWikidataFDO

Authors Stephen D. Miller, Noah Stephens-Davidowitz

Publication date 29 August 2019

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.05708

zbMATH Keywords

kissing numberlattice geometryGaussian masstransference bounds

Mathematics Subject Classification ID

Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Harmonic analysis in several variables (42B99)

Abstract: We generalize Banaszczyk's seminal tail bound for the Gaussian mass of a lattice to a wide class of test functions. From this we obtain quite general transference bounds, as well as bounds on the number of lattice points contained in certain bodies. As applications, we bound the lattice kissing number in $el{l}_p$ norms by $e^{(n+o(n))/p}$ for $0<pleq2$, and also give a proof of a new transference bound in the $el{l}_1$ norm.

Recommendations

• New bounds in some transference theorems in the geometry of numbers
• On a lemma of Minkowski
• Quick asymptotic upper bounds for lattice kissing numbers
• A New Transference Theorem in the Geometry of Numbers
• A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor

Cites work

• scientific article; zbMATH DE number 3633251 (Why is no real title available?)
• scientific article; zbMATH DE number 1445397 (Why is no real title available?)
• A mean value theorem in geometry of numbers
• A simple approach to asymptotic expansions for Fourier integrals of singular functions
• Fully homomorphic encryption using ideal lattices
• Inequalities for convex bodies and polar reciprocal lattices in \(\mathbb{R}^ n\)
• Lattice points in high-dimensional spheres
• Lattice problems in NP ∩ coNP
• Minima of Epstein's zeta function and heights of flat tori
• New bounds in some transference theorems in the geometry of numbers
• On Bounded Distance Decoding for General Lattices
• On lattices, learning with errors, random linear codes, and cryptography
• On the packing densities of superballs and other bodies
• Packing, coding, and ground states
• Probability laws related to the Jacobi theta and Riemann zeta functions, and Brownian excur\-sions
• Pseudorandomness of ring-LWE for any ring and modulus
• Public-key cryptosystems from the worst-case shortest vector problem
• Sieve algorithms for the shortest vector problem are practical
• Solving the shortest vector problem in \(2^n\) time using discrete Gaussian sampling (extended abstract)
• Systolic inequalities and Massey products in simply-connected manifolds
• Trapdoors for hard lattices and new cryptographic constructions
• Worst‐Case to Average‐Case Reductions Based on Gaussian Measures

Cited in

(5)

• Quantum algorithms for variants of average-case lattice problems via filtering
• New bounds in some transference theorems in the geometry of numbers
• Kissing numbers and the centered maximal operator
• On lattice constructions \(D\) and \(D^\prime\) from \(q\)-ary linear codes
• Measure inequalities and the transference theorem in the geometry of numbers

This page was built for publication: Kissing numbers and transference theorems from generalized tail bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5232155)