Computer Science/Discrete Mathematics Seminar II
Sensitivity Versus Block Sensitivity, I
There are two important measures of the complexity of a boolean function: the sensitivity and block sensitivity. Whether or not they are polynomial related remains a major open question. In this talk I will survey some known results on this conjecture, and its connection with various combinatorial problems.
Date & Time
March 12, 2013 | 10:30am – 12:30pm
Location
S-101Speakers
Affiliation
University of California, Los Angeles; Member, School of Mathematics