An Inequality for Gaussians on Lattices

DOI10.1137/15M1052226zbMath1395.11105arXiv1502.04796OpenAlexW3106397029MaRDI QIDQ5346551

Noah Stephens-Davidowitz, Oded Regev

Publication date: 24 May 2017

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

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

zbMATH Keywords

theta functionheat kernellatticesGaussian measure

Mathematics Subject Classification ID

Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Lattices and convex bodies (number-theoretic aspects) (11H06)

Related Items (11)

Dimension reduction techniques for the minimization of theta functions on lattices ⋮ Nonlinear algebra and applications ⋮ On computing high-dimensional Riemann theta functions ⋮ Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP) ⋮ Discrete Gaussian Distributions via Theta Functions ⋮ On a certain class of positive definite functions and measures on locally compact abelian groups and inner-product spaces ⋮ Euclidean lattices, theta invariants, and thermodynamic formalism ⋮ Theta Functions and Optimal Lattices for a Grid Cells Model ⋮ A \(2^{n/2}\)-time algorithm for \(\sqrt{n} \)-SVP and \(\sqrt{n} \)-Hermite SVP, and an improved time-approximation tradeoff for (H)SVP ⋮ A time-distance trade-off for GDD with preprocessing: instantiating the DLW heuristic ⋮ Minimal soft lattice theta functions

Cites Work

• A counterexample to monotonicity of relative mass in random walks
• Excursions in Brownian motion
• New bounds in some transference theorems in the geometry of numbers
• Probability laws related to the Jacobi theta and Riemann zeta functions, and Brownian excursions
• Solving the Shortest Vector Problem in 2 ⁿ Time Using Discrete Gaussian Sampling
• Trapdoors for hard lattices and new cryptographic constructions
• Fourier Transforms with Only Real Zeros
• A simple proof of the Gaussian correlation conjecture extended to multivariate gamma distributions
• The Restricted Isometry Property of Subsampled Fourier Matrices
• Worst‐Case to Average‐Case Reductions Based on Gaussian Measures

This page was built for publication: An Inequality for Gaussians on Lattices