Optimal Sample Exponents for Direct Discrete-Gaussian SVP Search on Haar Random Lattices
We determine the optimal sample exponent for direct discrete Gaussian SVP search on Haar random unimodular lattices, counting zero outputs. The output is one sampled vector, optionally divided by the greatest common divisor of its lattice coordinates. For every fixed approximation factor $1\leqγ<\sqrt e$, the exponent is $γ^2/(2e)-\logγ$ in natural logarithmic units; it is zero for $γ\geq\sqrt e$. For exact SVP this gives $0.2653689\ldots$ in base two. The converse permits arbitrary positive widths chosen from the lattice and all previous outputs, and a fixed width attains every exponent…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.30808
curl -X POST /api/v1/records/arxiv/2609.30808/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.30808/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'