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

Many approximation algorithms have been presented in the last decades
for hard search problems. The focus of this paper is on cryptographic
applications, where it is desired to design algorithms which do not
leak unnecessary information. Specifically, we are interested in
private approximation algorithms -- efficient algorithms ... more >>>

We prove that finding the solution of two player Nash Equilibrium is PPAD-complete.

more >>>