Solving Random Subset Sum Problem by $l_{p}$-norm SVP Oracle
Gengran Hu, Yanbin Pan, Feng Zhang · 2014
Abstract. 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 ∈ Z+, an lp-norm SVP oracle can be used to solve almost all random subset sum instances with density bounded by δp, where δ1 = 0.5761 and δp =