English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

$ \newcommand{\Z}{\mathbb{Z}} \newcommand{\eps}{\varepsilon}\newcommand{\cc}[1]{\mathsf{#1}} \newcommand{\NP}{\cc{NP}}\newcommand{\problem}[1]{\mathrm{#1}} \newcommand{\BDD}{\problem{BDD}}  $Bounded Distance Decoding $\BDD_{p,\alpha}$ is the problem of decoding alattice when the target point is promised to be within an $\alpha$ factor ofthe minimum distance of the lattice, in the $\ell_{p}$ norm. We prove that$\BDD_{p, \alpha}$ is $\NP$-hard under randomized reductions where $\alpha \to1/2$ as $p \to \infty$ (and for $\alpha=1/2$ when $p=\infty$), thereby showingthe hardness of decoding for distances approaching the unique-decoding radiusfor large $p$. We also show fine-grained hardness for $\BDD_{p,\alpha}$. Forexample, we prove that for all $p \in [1,\infty) \setminus 2\Z$ and constants$C > 1, \eps > 0$, there is no $2^{(1-\eps)n/C}$-time algorithm for$\BDD_{p,\alpha}$ for some constant $\alpha$ (which approaches $1/2$ as $p \to\infty$), assuming the randomized Strong Exponential Time Hypothesis (SETH).Moreover, essentially all of our results also hold (under analogous non-uniformassumptions) for $\BDD$ with preprocessing, in which unbounded precomputationcan be applied to the lattice before the target is available.  Compared to prior work on the hardness of $\BDD_{p,\alpha}$ by Liu,Lyubashevsky, and Micciancio (APPROX-RANDOM 2008), our results improve thevalues of $\alpha$ for which the problem is known to be $\NP$-hard for all $p >p_1 \approx 4.2773$, and give the very first fine-grained hardness for $\BDD$(in any norm). Our reductions rely on a special family of "locally dense"lattices in $\ell_{p}$ norms, which we construct by modifying theinteger-lattice sparsification technique of Aggarwal and Stephens-Davidowitz(STOC 2018).

Hardness of Bounded Distance Decoding on Lattices in $\ell_p$ Norms