Bounded Distance Decoding for Random Lattices
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908414741839872 |
|---|---|
| author | Gao, Shuhong |
| author_facet | Gao, Shuhong |
| contents | The current paper investigates the bounded distance decoding (BDD) problem for ensembles of lattices whose generator matrices have sub-Gaussian entries. We first prove that, for these ensembles the BDD problem is NP-hard in the worst case. Then, we introduce a polynomial-time algorithm based on singular value decomposition (SVD) and establish, both theoretically and through extensive experiments, that, for a random selected lattice from the same ensemble, the algorithm solves the BDD problem with high probability. To the best of our knowledge, this work provides the first example of a lattice problem that is NP-hard in the worst case yet admits a polynomial time algorithm on the average case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_16662 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Bounded Distance Decoding for Random Lattices Gao, Shuhong Computational Complexity 68Q25 (primary), 11H06 (secondary) F.2.2 The current paper investigates the bounded distance decoding (BDD) problem for ensembles of lattices whose generator matrices have sub-Gaussian entries. We first prove that, for these ensembles the BDD problem is NP-hard in the worst case. Then, we introduce a polynomial-time algorithm based on singular value decomposition (SVD) and establish, both theoretically and through extensive experiments, that, for a random selected lattice from the same ensemble, the algorithm solves the BDD problem with high probability. To the best of our knowledge, this work provides the first example of a lattice problem that is NP-hard in the worst case yet admits a polynomial time algorithm on the average case. |
| title | Bounded Distance Decoding for Random Lattices |
| topic | Computational Complexity 68Q25 (primary), 11H06 (secondary) F.2.2 |
| url | https://arxiv.org/abs/2506.16662 |