Improving Schroeppel and Shamir’s Algorithm for Subset Sum via Orthogonal Vectors

Speaker(s)

Karol Węgrzycki

Affiliation

MPI Saarbrucken

Date

Jan. 21, 2021, 12:15 p.m.

Information about the event

online

Seminar

Seminar Algorithms

---

We present an O^*(2^{0.5 n}) time and O^*(2^{0.249999n}) space randomized algorithm for Subset Sum. This is the first improvement over the long-standing O^*(2^{n/2}) time and O^*(2^{n /4}) space algorithm due to Schroeppel and Shamir. This talk will also feature an introduction to the representative families framework developed by Fomin, Lokshtanov, Panolan and Saurabh (J. ACM 2016) and representation technique introduced by Howgrave-Graham and Joux (EUROCRYPT 2010). Finally, we will uncover a tight and curious relation between the Subset Sum and Orthogonal Vectors problem. 

---