April 25, 2017, 10:15 a.m.
[COG seminar] Marcin Mucha on "Problems equivalent to (min,+)-convolution"
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 (https://arxiv.org/abs/1702.07