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

Jesper Nederlof; Karol Wegrzycki

doi:10.1145/3406325.3451024

STOC2021顶会

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

Jesper Nederlof, Karol Wegrzycki

arXiv DOI 出版方

2021年份

8顶会引用

摘要

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).