Complexity seminar
Adventures in Monotone Complexity and TFNP
Lukáš Folwarczný
IM CAS
Friday, 15. November 2019 - 13:30 to 15:00
in IM, rear building, ground floor
In this talk, I present the main ideas from the paper Adventures in Monotone Complexity and TFNP by Mika Göös, Pritish Kamath, Robert Robere, and Dmitry Sokolov. The main focus of the talk will be on the relations between monotone computational models and communication complexity (going from Karchmer-Wigderson (formulas) and Razborov (circuits) to this paper (span programs)).