Kissing Numbers and Transference Theorems from Generalized Tail Bounds

DOI10.1137/18M1210186zbMATH Open1422.52006arXiv1802.05708OpenAlexW2962963352WikidataQ127437215 ScholiaQ127437215MaRDI QIDQ5232155FDOQ5232155

Noah Stephens-Davidowitz, Stephen D. Miller

Publication date: 29 August 2019

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

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.

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)

Cites Work

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

Cited In (4)

• On lattice constructions \(D\) and \(D^\prime\) from \(q\)-ary linear codes
• 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

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)