April 25, 2017, 10:15 a.m.

Tuesday, 10:15, room 310.

Abstract: In recent years, many attempts have been made to explain apparent hardness of polynomially solvable problems by introducing new hardness assumptions: SAT, 3SUM, APSP, etc. I will briefly survey this area and then discuss a very recent paper (, joint work with Marek Cygan, Karol Wegrzycki and Michal Wlodarczyk, to appear at ICALP 2017), in which we explore using the (min,+)-convolution problem as a hardness assumption. Among other things, we are able to use this assumption to show that it is not possible to (significantly) improve over the classical DP algorithms for Knapsack.