Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > KNAPSACKS:
Reports tagged with knapsacks:
TR05-142 | 1st December 2005
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 >>>