Complexity seminar

Linear separation complexity of a random function

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