Friday 4/05 Colloquium - Tim Randolph '18

Friday, April 05
2:35pm in Wege (TCL 123)
Algorithmic Approaches to Subset Sum (and Other Hard Problems)
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.
Tim Randolph is a graduating PhD student in the Department of Computer Science at Columbia University. His research interests lie at the intersection of computer science and mathematics and focus on bringing new mathematical tools to bear on hard problems in exact and parameterized complexity. In addition to work in algorithms, he has also published peer-reviewed research on cryptography, mathematics, management science and computer science education. He has a special interest in promoting equity and inclusion in computer science.