Solving this problem in pseudopolynomial time with polynomial space: Daniel Lokshtanov and Jesper Nederlof: "Saving Space by Algebraization". To appear in the proceedings of ACM Symposium on Theory of Computing (STOC 2010).

The next reference solves this problem (even general knapsack, I believe). An 2^{0.311 n} Algorithm: Nick Howgrave-Graham and Antoine Joux : "A new generic algorithm for hard knapsacks". To appear in the proceedings of EUROCRYPT 2010.

However, the problem might be easily adjusted to "find an algorithm that takes O(2^{c n}) time, where c < 0.311", etc etc.


Comments are limited to a maximum of 1000 characters.
More information about formatting options