Algebraic Techniques for Combinatorial Problems
Amit K S
Given a multiset of n positive integers and a target integer t, the
SubsetSum problem asks to determine whether there exists a subset of S
that sums up to t. Bringmann (SODA'17) gave a randomized O(n+t) time
algorithm (hiding polylogarithmic factors) which is believed to be near
optimal. In this paper, Jin and Wu (Wu is a high school student in China!)
give a very simple and elegant randomized algorithm matching the running
time of Bringmann.
This paper follows the approach of using algebraic techniques
(manipulating polynomials) to design faster algorithms for hard
combinatorial problems. Time permitting, we shall discuss some of the
other recent applications of this approach.