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.
login/create account
Drupal
CSI of Charles University
Updates
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.