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
Video Link:https://video.ias.edu/csdm/1213/0312-HaoHuang

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.