Week 10 Activity (Tuesday): Colloquium talk at Mudd

This week, Harvey Mudd College hosts a talk by Tim Randolph, from Columbia University, who is a candidate for a faculty position in the CS department at the college. The talk begins at 4:15 PM on Tuesday, but a reception with refreshments will be held outside at 4:00 PM.

There are two colloquium talks this week, so we have slightly different rules for this week for students enrolled in CS Colloquium (CS 195).

• We would be hugely pleased to have you attend both talks. These talks don't only let us see a faculty candidate, they also let the faculty candidate see us, so having a good audience is important. But if you can only manage to see a single talk this week, that is okay too.
• If you are in Section 1, we know you're free for our other talk (which is at the usual time on Thursday), but if you're free to attend this talk, feel free to do so, either as well or instead.
• If you are in Section 2, and you can attend this talk live and in person in its timeslot, we would be strongly encourage you to do so.

Algorithmic Approaches to Subset Sum (and Other Hard Problems)

Abstract

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.

About Tim Randolph

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.

When and How to Attend

• Tuesday, October 31
  • Location: Galileo McAlister, Harvey Mudd College
  • Optional reception begins at 4:00 PM
  • Talk runs from 4:15–5:30 PM

Recording for Section 2

Required Assessment

To receive credit for attending this colloquium, complete the assessment:

• Assessment

Please do so at your soonest convenience, within 24 hours of seeing the talk.

(When logged in, completion status appears here.)

Go to Parent Page Next Page