Improving Schroeppel and Shamir's algorithm for subset sum via orthogonal vectors

We present an O∗(20.5n) time and O∗(20.249999n) space randomized algorithm for solving worst-case Subset Sum instances with n integers. This is the first improvement over the long-standing O∗(2n/2) time and O∗(2n/4) space algorithm due to Schroeppel and Shamir (FOCS 1979).