I recently learned about a new class of seemingly complicated, but in fact very simple functions which are called by several names, but perhaps most commonly as NCF Boolean functions (NCF is an abbreviation for “nested canalyzing function,” a term used by mathematical biologists). These functions were independently introduced by theoretical computer scientists in the 1960s using the term unate cascade functions. As described in [JRL2007] and [LAMAL2013], these functions have applications in a variety of scientific fields. This post describes these functions.

A Boolean function of n variables is simply a function . Denote the -vector space of such functions by . We write an element of this space as , where the variables will be called coordinate variables. Let

denote the restriction map sending to . In this post, the cosets

will be called coordinate hyperplanes (). A function in which is constant along some coordinate hyperplane is called canalyzing. An NCF function is a function which (a) is constant along some coordinate hyperplane , (b) whose restriction is constant along some coordinate hyperplane , (c) whose restriction is constant along some coordinate hyperplane , (d) and so on. This “nested” inductive definition might seem complicated, but to a computer it’s pretty simple and, to boot, it requires little memory to store.

If and then let denote the vector whose i-th coordinate is flipped (bitwise). The sensitivity of at is
. Roughly speaking, it’s the number of single-bit changes in that change the value of . The (maximum) sensitivity is the quantity
The block sensitivity is defined similarly, but you allow blocks of indices of coordinates to by flipped bitwise, as opposed to only one. It’s possible to

• compute the sensitivity of any NCF function,
• show the block sensitivity is equal to the sensitivity,
• compute the cardinality of the set of all monotone NCF functions.

For details, see for example Li and Adeyeye [LA2012].

REFERENCES
[JRL2007] A.S. Jarrah, B. Raposa, R. Laubenbachera, “Nested Canalyzing, Unate Cascade, and Polynomial Functions,” Physica D. 2007 Sep 15; 233(2): 167–174.

[LA2012] Y. Li, J.O. Adeyeye, “Sensitivity and block sensitivity of nested canalyzing function,” ArXiV 2012 preprint. (A version of this paper was published later in Theoretical Comp. Sci.)

[LAMAL2013] Y. Li, J.O. Adeyeye, D. Murrugarra, B. Aguilar, R. Laubenbacher, “Boolean nested canalizing functions: a comprehensive analysis,” ArXiV, 2013 preprint.