Chennai Mathematical Institute

Seminars




On the sensitivity of Cyclically Invariant boolean functions
Sourav Chakraborty
Univ. of Chicago.
09-08-04


Abstract

"Sensitivity" and "block sensitivity" are various measures of the boolean functions. In short they measure the number of bits on which a function is sensitive. We look at cyclically invariant boolean functions and try to find out the sensitivity of these functions.

The whole talk only uses simple combinatorics and hence should be understandable by everyone.