MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

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

Karol Wegrzycki
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience
English

Date, Time and Location

Tuesday, 12 January 2021
13:00
30 Minutes
Virtual talk
Virtual talk
Saarbrücken

Abstract

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.


--------------------
Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.

Contact

Sándor Kisfaludi-Bak
--email hidden
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.

Sándor Kisfaludi-Bak, 12/10/2020 16:41
Sándor Kisfaludi-Bak, 12/10/2020 16:40 -- Created document.