25 kwietnia 2017 10:15

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 (, 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.