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