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

Recent work [BGS17,ABGS19] has shown SETH hardness of CVP in the $\ell_p$norm for any $p$ that is not an even integer. This result was shown by giving aKarp reduction from $k$-SAT on $n$ variables to CVP on a lattice of rank $n$.In this work, we show a barrier towards proving a similar result for CVP in the$\ell_p$ norm where $p$ is an even integer. We show that for any $c>0$, if forevery $k > 0$, there exists an efficient reduction that maps a $k$-SAT instanceon $n$ variables to a CVP instance for a lattice of rank at most $n^{c}$ in theEuclidean norm, then $\mathsf{coNP} \subset \mathsf{NP/Poly}$. We prove asimilar result for CVP for all even norms under a mild additional promise thatthe ratio of the distance of the target from the lattice and the shortestnon-zero vector in the lattice is bounded by $exp(n^{O(1)})$.  Furthermore, we show that for any $c> 0$, and any even integer $p$, if forevery $k > 0$, there exists an efficient reduction that maps a $k$-SAT instanceon $n$ variables to a $SVP_p$ instance for a lattice of rank at most $n^{c}$,then $\mathsf{coNP} \subset \mathsf{NP/Poly}$. The result for SVP does notrequire any additional promise.  While prior results have indicated that lattice problems in the $\ell_2$ norm(Euclidean norm) are easier than lattice problems in other norms, this is thefirst result that shows a separation between these problems.  We achieve this by using a result by Dell and van Melkebeek [JACM, 2014] onthe impossibility of the existence of a reduction that compresses an arbitrary$k$-SAT instance into a string of length $\mathcal{O}(n^{k-\epsilon})$ for any$\epsilon>0$. In addition to CVP, we also show that the same result holds forthe Subset-Sum problem using similar techniques.

Why we couldn't prove SETH hardness of the Closest Vector Problem for even norms!