|Computer Science/Discrete Mathematics Seminar II|
|Topic:||Sensitivity Versus Block Sensitivity, I|
|Affiliation:||University of California, Los Angeles; Member, School of Mathematics|
|Date:||Tuesday, March 12|
|Time/Room:||10:30am - 12:30pm/S-101|
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.