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

We prove that the Minimum Distance Problem (MDP) on linear codes over anyfixed finite field and parameterized by the input distance bound is W[1]-hardto approximate within any constant factor. We also prove analogous results forthe parameterized Shortest Vector Problem (SVP) on integer lattices.Specifically, we prove that SVP in the $\ell_p$ norm is W[1]-hard toapproximate within any constant factor for any fixed $p >1$ and W[1]-hard toapproximate within a factor approaching $2$ for $p=1$. (We show hardness underrandomized reductions in each case.)  These results answer the main questions left open (and explicitly posed) byBhattacharyya, Bonnet, Egri, Ghoshal, Karthik C. S., Lin, Manurangsi, and Marx(Journal of the ACM, 2021) on the complexity of parameterized MDP and SVP. ForMDP, they established similar hardness for binary linear codes and left thecase of general fields open. For SVP in $\ell_p$ norms with $p > 1$, theyshowed inapproximability within some constant factor (depending on $p$) andleft open showing such hardness for arbitrary constant factors. They also leftopen showing W[1]-hardness even of exact SVP in the $\ell_1$ norm.

Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all $\ell_p$ Norms