slideshow 3

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)).