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

Prelegent(ci)

Karol Węgrzycki

Afiliacja

MPI Saarbrucken

Termin

21 stycznia 2021 12:15

Informacje na temat wydarzenia

online

Seminarium

Seminarium "Algorytmika"

---

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. 

---