Subset Sum in $O(2^{0.49n})$ time. Gives a uniform randomized classical algorithm for worst-case Subset Sum in ordinary $O(2^{0.49n})$ word-RAM time on polynomial-bit inputs, where n counts the integers. The time bound holds on every execution and success probability is at least 2/3 on every input. Inputs may repeat positive integers; words have $O(n+b)$ bits for maximum input bit length b.
released 2026-10-04 | 3 theorems · 7 lemmas · 10 proofs · 14,587 words |
PLAY LEVEL 1 »(pdf)
We give a uniform randomized classical algorithm for Subset Sum with bounded error and worst-case running time $O(2^{0.49n})$ on polynomial-bit inputs in a word-RAM model, where n is the number of input integers. The time bound holds on every random execution.
released 2026-09-26 | 1 theorem · 11 lemmas · 12 proofs · 17,517 words |
PLAY LEVEL 2 »(pdf)
We give a uniform classical randomized decision algorithm for worst-case Subset Sum. Under every fixed polynomial bound on input-integer bit length, it uses $\mathop{\mathrm{poly}}\nolimits (n)2^{n/2}$ time and ordinary $O(2^{n/5})$ writable words of $O(n+b)$ bits, where b is the largest input bit length. Both resource bounds hold on every execution. The error is one-sided: the algorithm always rejects unsolvable instances and accepts each solvable instance with probability at least 2/3.