Maximal sensitivity of Boolean nested canalizing functions (Q2272408)

The paper under review concerns properties of a class of Boolean functions called NCF Boolean functions (NCF is an abbreviation for ``nested canalyzing function'') or unate cascade functions. They are used in a variety of applications, ranging from mathematical biology to efficient computer circuit design. Denote the set of Boolean functions of \(n\) variables \(f\colon \mathrm{GF}(2)^n\to \mathrm{GF}(2)\) by \(B(n)\). Let \(\operatorname{Res}_{x_i=a}\colon B(n)\to B(n-1)\) denote restriction to the coordinate hyperplane \(H_{i,a,n}= \{x=(x_1,x_2,\dots,x_n) \in \mathrm{GF}(2)^n\mid x_i=a\}\) \((a \in \mathrm{GF}(2)\), \(1\le i\le n)\). A function in \(B(n)\) which is constant along some coordinate hyperplane is called canalyzing. An NCF function is a function \(f\in B(n)\) which (a) is constant along some coordinate hyperplane \(H_{i_1,a_1,n}\), (b) whose restriction \(f_1 = \operatorname{Res}_{x_{i_1}=a_1}(f)\in B(n-1)\) is, in turn, constant along some coordinate hyperplane \(H_{i_2,a_2,n-1}\subset \mathrm{GF}(2)^{n-1}\), (c) whose restriction \(f_2 = \operatorname{Res}_{x_{i_2}=a_2}(f_1)\in B(n-2)\) is, in turn, constant along some coordinate hyperplane \(H_{i_2,a_2,n-2}\subset \mathrm{GF}(2)^{n-2}\), and so on. This ``nested'' inductive definition might be complicated to write down carefully, but simple for a computer and, in addition, it requires little memory to store. In a rough sense, these form a very efficient class of Boolean functions. All this is stated more explicitly in the paper under review. If \(1\leq i\leq n\) and \(x=(x_1,x_2,\dots,x_n) \in \mathrm{GF}(2)^n\) then let \(x^i\in \mathrm{GF}(2)^n\) denote the vector whose \(i\)-th coordinate is flipped (bitwise). The sensitivity of \(f\in B(n)\) at \(x\) is \(s(f,x) = |\{i\ |\ 1\leq i\leq n,\ f(x)\ne f(x^i)\}|\). The sensitivity of $f$ is the quantity $s(f)=max_x s(f,x)$. The block sensitivity is defined similarly, but you allow blocks of indices of coordinates to by flipped bitwise, as opposed to only one. The main tasks of the article under review are as follows. \begin{itemize} \item Explicitly compute the sensitivity of any Boolean NCF. \item Show the block sensitivity is equal to the sensitivity for any Boolean NCF. \item Compute the cardinality of the set of all monotone NCF functions. \end{itemize} The explicit formulas are too complicated to state in this review but are clearly presented in the author's paper.