Lecture: Curious Facts About Nested Canalyzing Functions

Richard Edwin Stearns

Abstract:

If f is a binary valued function of binary variables, one of its variables v is called a “canalyzing variable” if the function can be described as follows: IF v=a THEN f=b ELSE f is a function of the remaining variables. If the “function of the remaining variables” itself has a canalyzing variable and so forth, the function is called a “nested canalyzing function” or “NCF”. Because of the nesting, it is often the case that the solution to a computational problem for (n+1)-parameter NCFs is easy to obtain from the solution for n-parameter NCFs and by induction easy to solve for all NCFs. Because of this computational simplicity, it is easy to study NCFs experimentally by working out examples and looking for patterns. Analysis of the associated algorithms can then provide algebra for proving any resulting conjectures.
In this talk, we discuss two such discoveries. One is the appearance of Fibonacci numbers when representing an NCF by a threshold gate. The other is a characterization of the NCFs with the worst average sensitivity and the asymmetry between odd numbered variables and even numbered variables.

---