Publications from 2010 on this topic: Pseudopolynomial algorithm with only 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).

Fast knapsack: Nick Howgrave-Graham and Antoine Joux: "New Generic Algorithms for Hard Knapsacks". To appear in the proceedings of EUROCRYPT 2010 The running time is O^*(2^0.311 n), which is faster than the question posted here.

Obviously, the question could become: find a lower constant than 0.311.


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