25 kwietnia 2017 10:15
[Seminarium ZOK] Marcin Mucha on "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.07