Computer Science Colloquium - Tim Randolph '18

The Subset Sum problem is the most fundamental NP-complete problem concerned with adding numbers together. However, progress on exact algorithms for this problem has been slow: Since Horowitz and Sahni’s 1974 invention of the “Meet-in-the-Middle” approach, our best algorithms have relied on simple enumeration and dynamic programming strategies. The lack of an algorithm for Subset Sum that leverages our modern understanding of addition points to important gaps in our knowledge about the behavior of the integers.

In this talk, I’ll give an overview of my work on this important problem, in the context of a broader research approach that uses algorithms for hard problems as a gateway to a better understanding of mathematical primitives and data objects. First, I’ll discuss recent progress on exact algorithms for “random-like” instances of Subset Sum. Second, I’ll introduce a new parameterization of the problem that allows Subset Sum instances with significant “additive structure” to be solved efficiently. Finally, I’ll sketch a “structure vs. randomness” approach that powers the fastest known algorithm for Subset Sum and might lead to exponential runtime speed-ups in the future.