Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Equal-Subset-Sum Faster Than the Meet-in-the-Middle
Speaker:Karol Wegrzycki
coming from:University of Warsaw
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 12 November 2019
Duration:30 Minutes
Building:E1 4
In the Equal-Subset-Sum problem, we are given a set S of n integers and the problem is to decide if there exist two disjoint nonempty subsets A,B of S whose elements sum up to the same value. The problem is NP-complete. The state-of-the-art algorithm runs in O(3^{n/2}) = O(1.7321^n) time and is based on the meet-in-the-middle technique. In this paper, we improve upon this algorithm and give O(1.7088^n) worst case Monte Carlo algorithm. This answers a question suggested by Woeginger in his inspirational survey.

Additionally, we analyse the polynomial space algorithm for Equal-Subset-Sum. A naive polynomial space algorithm for Equal-Subset-Sum runs in O(3^n) time. With read-only access to exponentially many random bits, we show a randomized algorithm running in O(2.6817^n) time and polynomial space.

Joint work with Marcin Mucha, Jesper Nederlof and Jakub Pawlewicz.

Name(s):Karl Bringmann
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Karl Bringmann, 11/06/2019 04:42 PM
  • Karl Bringmann, 11/06/2019 04:41 PM -- Created document.