Block sensitivity of weakly symmetric functions

DOI10.1016/J.TCS.2007.05.020MaRDI QIDQ2382286zbMATH OpenOpenAlexFDO

Authors Xiaoming Sun

Publication date 28 September 2007

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2007.05.020

zbMATH Keywords

block sensitivityBoolean functionweakly symmetric function

Mathematics Subject Classification ID

Boolean functions (06E30) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25)

Review text

\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)\).

Recommendations

• Theory and Applications of Models of Computation
• Block sensitivity of minterm-transitive functions
• Sensitivities and block sensitivities of elementary symmetric Boolean functions
• Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
• Sensitivity vs. block sensitivity of Boolean functions

Cites work

• Complexity measures and decision tree complexity: a survey.
• CREW PRAM<scp>s</scp> and Decision Trees
• On recognizing graph properties from adjacency matrices
• On the degree of Boolean functions as real polynomials
• Quantum lower bounds by polynomials
• The critical complexity of graph properties

Cited in

(8)

• Minterm-transitive functions with asymptotically smallest block sensitivity
• On block sensitivity and fractional block sensitivity
• Sensitivities and block sensitivities of elementary symmetric Boolean functions
• Certificate complexity of elementary symmetric Boolean functions
• On the sensitivity of cyclically-invariant Boolean functions
• Theory and Applications of Models of Computation
• Separations between combinatorial measures for transitive functions
• Block sensitivity of minterm-transitive functions

This page was built for publication: Block sensitivity of weakly symmetric functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2382286)