News for hackers. Stuff that matters.
Re:Faster Space-Efficient Algorithms for Subset Sum, K-Sum a... by nerdponx on Friday December 09, 2016 @09:03AM (#13138766)
How much better is this than prior art?
Re:Faster Space-Efficient Algorithms for Subset Sum, K-Sum a... by bradleyjg on Friday December 09, 2016 @10:49AM (#13139356)
In pure time terms it is worse, as the best prior was O$(2^.5n). However, that algorithm took O$(2^.25n) space. This algorithm uses only polynomial space but runs in O$(2^.86n) time. The naive solution runs in O$(2^n) and polynomial space.

I believe this top line result will mostly be of interest to Computer Scientists, as a practical matter these problems are rarely solved exactly because even the fast algorithms are far too slow for non-trivial problem sizes.

However, this part regarding the "list disjointment problem" may be of wider interest:

"Underlying these results is an algorithm that determines whether two given lists of length n with integers bounded by a polynomial in n share a common value. Assuming random read-only access to random bits, we show that this problem can be solved using O(log n) space significantly faster than the trivial O(n^2) time algorithm if no value occurs too often in the same list."

N.B. The HN parser won't let me use stars, so read star for each of the dollar signs in the first paragraph.

Re:Faster Space-Efficient Algorithms for Subset Sum, K-Sum a... by the8472 on Friday December 09, 2016 @11:33AM (#13139687)
you could use the multiplication sign × or the middle dot ·
Re:Faster Space-Efficient Algorithms for Subset Sum, K-Sum a... by IanCal on Friday December 09, 2016 @12:58PM (#13140386)
The star here is not a multiplication. A bit more info on O star http://math.stackexchange.com/questions/672281/what-is-the-d...
Re:Faster Space-Efficient Algorithms for Subset Sum, K-Sum a... by the8472 on Friday December 09, 2016 @01:18PM (#13140568)
Ah well, then there's the mathematical asterisk operator O∗ (U+2217) which is separate from the ascii asterisk O* and you could also use the "combining asterisk above" O ⃰ (O, whitespace, combining char) although that's probably abuse of the characters.

The rules say

> Text surrounded by asterisks is italicized, if the character after the first asterisk isn't whitespace.

But apparently noen of the zero-width spaces are not counted as whitespace.

Re:Faster Space-Efficient Algorithms for Subset Sum, K-Sum a... by jsc on Friday December 09, 2016 @02:14PM (#13141008)
This is actually slower than previous art, but with proven complexity. Namely the algorithm in http://eprint.iacr.org/2011/474.pdf runs in time 2^0.72n and constant memory, but is heuristic only.
Re:Faster Space-Efficient Algorithms for Subset Sum, K-Sum a... by AstralStorm on Saturday December 10, 2016 @04:03AM (#13144798)
Apples, oranges. We have heuristic algorithms for knapsack running in polynomial time. The trick is that because they are heuristic, they do not necessarily solve the problem.