The generalized knapsack problem is the following: given $m$ random elements $a_1,\ldots,a_m\in R$ for some ring $R$, and a target $t\in R$, find elements $z_1,\ldots,z_m\in D$ such that $\sum{a_iz_i}=t$ where $D$ is some given subset of $R$. In (Micciancio, FOCS 2002), it was proved that for appropriate choices of $R$ ... more >>>

In the Subset Sum problem, we are given n integers a_1,...,a_n and a target number t, and are asked to find the subset of the a_i's such that the sum is t. A version of the subset sum problem is the Random Modular Subset Sum problem. In this version, the ... more >>>