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 Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

It is well known that almost all random subset sum instances with density less than 0.6463... can be solved with an l2-norm SVP oracle by Lagarias and Odlyzko. Later, Coster et al. improved the bound to 0.9408... by using a different lattice. In this paper, we generalize this classical result to lp-norm. More precisely, we show that for p∈i¾?+, an lp-norm SVP oracle can be used to solve almost all random subset sum instances with density bounded by i¾?p, where i¾?1=0.5761 and $\delta_p = 1/\frac{1}{2^p}\log_22^{p+1}-2+\log_21+\frac{1}{2^p-11-\frac{1}{2^{p+1}-2}^{2^p-1}}$ for pi¾?3asymptotically, i¾?pi¾?2p/p+2. Since i¾?p goes increasingly to infinity when p tends to infinity, it can be concluded that an lp-norm SVP oracle with bigger p can solve more subset sum instances. An interesting phenomenon is that an lp-norm SVP oracle with pi¾?3 can help solve almost all random subset sum instances with density one, which are thought to be the most difficult instances.

Solving Random Subset Sum Problem by l p -norm SVP Oracle