slideshow 3

Complexity seminar

Linear separation complexity of a random function

Pavel Hrubes
IM CAS

 

Friday, 18. March 2022 - 14:00 to 15:30

in IM, rear building, ground floor

Linear separation complexity of a Boolean function is a measure of how hard it is to distinguish accepting and rejecting inputs by means of a linear program. I will discuss nontrivial upper and lower bounds on separation complexity of a random function.

Joint work with Navid Talebanfard