Exact ℓ_p-CVP reduced to Euclidean SVP in polynomial space
Original title: Exact $\ell_p$-CVP via Euclidean SVP in Polynomial Space
The reduction enables polynomial-space algorithms for exact ℓ_p-CVP using existing SVP solvers, with time bounds N^{N/(2e)+o(N)} for p=2.
A randomized rank-preserving reduction from exact ℓ_p-CVP to exact Euclidean SVP is given for every integer p≥2. For rational inputs of bit length ℓ on full-rank lattices, it uses (Cp)^N poly(p,ℓ) oracle calls and poly(p,ℓ) working space. For p=2 it transfers known SVP algorithms to CVP; for p≥3 it yields algorithms with 2^{O(N)} time or N^{N/(4e)+o(N)} time and polynomial space. The approach performs sequential local search over cosets of 2L while tracking objective excess and uses sparsification-based sampling.
- Reduction uses (Cp)^N poly(p,ℓ) SVP oracle calls
- poly(p,ℓ) working space outside oracles
- For p=2: N^{N/(2e)+o(N)} time with Kannan/Feng-Gao-Liu
- For fixed p≥3: 2^{O(N)} or N^{N/(4e)+o(N)} randomized time
- Midpoint inequalities and sparsification sampler used
From the original article
1 min read at arxiv.orgWe give a randomized, rank-preserving reduction from exact $\ell_p$-CVP to exact Euclidean SVP for every integer $p\ge2$. For rational inputs of bit length $\ell$ on full-rank lattices $L\subset\mathbb R^N$, the reduction uses $(Cp)^N\poly(p,\ell)$ oracle calls and additional bit operations, where $C$ is an absolute constant.
By Jiseung Kim · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.