School of Mathematics
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.
I will continue the exposition of different derandmization techniques for probabilistic logspace algorithms.