TY - UNPB

T1 - Improving Schroeppel and Shamir's Algorithm for Subset Sum via Orthogonal Vectors

AU - Nederlof, Jesper

AU - Węgrzycki, Karol

N1 - STOC 2021, 38 pages, 3 figures

PY - 2020/10/16

Y1 - 2020/10/16

N2 - We present an $\mathcal{O}^\star(2^{0.5n})$ time and $\mathcal{O}^\star(2^{0.249999n})$ space randomized algorithm for solving worst-case Subset Sum instances with $n$ integers. This is the first improvement over the long-standing $\mathcal{O}^\star(2^{n/2})$ time and $\mathcal{O}^\star(2^{n/4})$ space algorithm due to Schroeppel and Shamir (FOCS 1979). We breach this gap in two steps: (1) We present a space efficient reduction to the Orthogonal Vectors Problem (OV), one of the most central problem in Fine-Grained Complexity. The reduction is established via an intricate combination of the method of Schroeppel and Shamir, and the representation technique introduced by Howgrave-Graham and Joux (EUROCRYPT 2010) for designing Subset Sum algorithms for the average case regime. (2) We provide an algorithm for OV that detects an orthogonal pair among $N$ given vectors in $\{0,1\}^d$ with support size $d/4$ in time $\tilde{O}(N\cdot2^d/\binom{d}{d/4})$. Our algorithm for OV is based on and refines the representative families framework developed by Fomin, Lokshtanov, Panolan and Saurabh (J. ACM 2016). Our reduction uncovers a curious tight relation between Subset Sum and OV, because any improvement of our algorithm for OV would imply an improvement over the runtime of Schroeppel and Shamir, which is also a long standing open problem.

AB - We present an $\mathcal{O}^\star(2^{0.5n})$ time and $\mathcal{O}^\star(2^{0.249999n})$ space randomized algorithm for solving worst-case Subset Sum instances with $n$ integers. This is the first improvement over the long-standing $\mathcal{O}^\star(2^{n/2})$ time and $\mathcal{O}^\star(2^{n/4})$ space algorithm due to Schroeppel and Shamir (FOCS 1979). We breach this gap in two steps: (1) We present a space efficient reduction to the Orthogonal Vectors Problem (OV), one of the most central problem in Fine-Grained Complexity. The reduction is established via an intricate combination of the method of Schroeppel and Shamir, and the representation technique introduced by Howgrave-Graham and Joux (EUROCRYPT 2010) for designing Subset Sum algorithms for the average case regime. (2) We provide an algorithm for OV that detects an orthogonal pair among $N$ given vectors in $\{0,1\}^d$ with support size $d/4$ in time $\tilde{O}(N\cdot2^d/\binom{d}{d/4})$. Our algorithm for OV is based on and refines the representative families framework developed by Fomin, Lokshtanov, Panolan and Saurabh (J. ACM 2016). Our reduction uncovers a curious tight relation between Subset Sum and OV, because any improvement of our algorithm for OV would imply an improvement over the runtime of Schroeppel and Shamir, which is also a long standing open problem.

KW - cs.DS

KW - cs.CC

U2 - 10.48550/arXiv.2010.08576

DO - 10.48550/arXiv.2010.08576

M3 - Preprint

SP - 1

EP - 38

BT - Improving Schroeppel and Shamir's Algorithm for Subset Sum via Orthogonal Vectors

PB - arXiv

ER -