|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Fine-grained hardness of CVP(P)--- Everything that we can prove (and nothing else) | | Divesh Aggarwal
; Huck Bennett
; Alexander Golovnev
; Noah Stephens-Davidowitz
; | | Date: |
6 Nov 2019 | | Abstract: | We show that the Closest Vector Problem in the $ell_p$ norm
($mathrm{CVP}_p$) cannot be solved in $2^{(1-varepsilon)n}$ time for all $p
otin 2mathbb{Z}$ and $varepsilon > 0$ (assuming SETH). In fact, we show
that the same holds even for (1)~the approximate version of the problem
(assuming a gap version of SETH); and (2) $mathrm{CVP}_p$ with preprocessing,
in which we are allowed arbitrary advice about the lattice (assuming a
non-uniform version of SETH). For "plain" $mathrm{CVP}_p$, the same hardness
result was shown in [Bennett, Golovnev, and Stephens-Davidowitz FOCS 2017] for
all but finitely many $p
otin 2mathbb{Z}$, where the set of exceptions
depended on $varepsilon$ and was not explicit. For the approximate and
preprocessing problems, only very weak bounds were known prior to this work.
We also show that the restriction to $p
otin 2mathbb{Z}$ is in some sense
inherent. In particular, we show that no "natural" reduction can rule out even
a $2^{3n/4}$-time algorithm for $mathrm{CVP}_2$ under SETH. For this, we prove
that the possible sets of closest lattice vectors to a target in the $ell_2$
norm have quite rigid structure, which essentially prevents them from being as
expressive as $3$-CNFs. | | Source: | arXiv, 1911.2440 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER