演讲人： Chao Xu University of Illinois at Urbana-Champaign
时间： 2017-07-06 10:30-2017-07-06 11:30
地点： FIT 1-222
内容：
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.
