Speaker: Chao Xu University of Illinois at Urbana-Champaign
Time: 2017-07-06 10:30-2017-07-06 11:30
Venue: FIT 1-222

Abstract:

Given a set S of n positive integers and a target integer t, the subset sum problem is to decide if there is a subset of S that sums up to t. 

We present a divide-and-conquer algorithm that computes all the realizable subset sums up to an integer u in Õ(min{n√u,u^{4/3},σ}), where σ is the sum of all elements in S and Õ hides polylogarithmic factors. 

We also present a modified algorithm for integers mod m, which computes all the realizable subset sums within the group in O˜(min{n√m,m^{5/4}}) time. 

The algorithm also solves a problem in codes that correcting limited-magnitude errors.

The talk is based on joint work with Konstantinos Koiliaris.