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.

You must be logged in to post a comment.