25 kwietnia 2017 10:15
[Seminarium ZOK] Marcin Mucha: Problems equivalent to (min,+)-convolution
Wtorek, 10:15, sala 310.
Streszczenie: 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 (https://arxiv.org/abs/1702.07669, 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.