A Low-Space Algorithm for Worst-Case Subset Sum

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 $\mathrm{poly}(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.