Block sensitivity of weakly symmetric functions (Q2382286): Difference between revisions

\textit{N. Nisan} [SIAM J. Comput. 20, No. 6, 999--1007 (1991; Zbl 0737.68028)] introduced the concept of block sensitivity of a Boolean function \(f\), denoted by \(\text{bs}(f)\), proved tight bounds for computing \(\text{bs}(f)\) on a CREW PRAM and showed that block sensitivity is polynomially related to many other measures of complexity. This is one of the most useful measures of Boolean functions. In this paper the block sensitivity of weakly symmetric functions (functions invariant under some transitive group action) is investigated and it is proved that for any nontrivial weakly symmetric function \(f\), \(\text{bs}(f)\geq N^{\frac{1}{3}}\) and there exists a cyclically invariant function \(f\) such that \(\text{bs}(f)=O(N^{\frac{3}{7}}\log N)\).