Family 138Theoretical computer scienceNo LeanNot yet digested

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.

Manuscripts in this family · 2

Subset Sum in Time $O(2^{0.49n})$

Oct 4, 2026·subset-sum.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.

Full abstract

PDF on GitHub LaTeX source

A Low-Space Algorithm for Worst-Case Subset Sum

Sep 26, 2026·paper.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.