Sensitivity Versus Block Sensitivity, I
| Computer Science/Discrete Mathematics Seminar II | |
| Topic: | Sensitivity Versus Block Sensitivity, I |
| Speaker: | Hao Huang |
| 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.