Subset Sum in Time $2^{n/2}/poly(n)$

Xi Chen, Yaonan Jin, Tim Randolph +1

A major goal in the area of exact exponential algorithms is to give an algorithm for the (worst-case) $n$-input Subset Sum problem that runs in time $2^{(1/2-c)n}$ for some const…