We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

5th HLF – Lecture: Curious Facts About Nested Canalyzing Functions

Formal Metadata

Title
5th HLF – Lecture: Curious Facts About Nested Canalyzing Functions
Title of Series
Number of Parts
49
Author
Contributors
License
No Open Access License:
German copyright law applies. This film may be used for your own use but it may not be distributed via the internet or passed on to external parties.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
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. The opinions expressed in this video do not necessarily reflect the views of the Heidelberg Laureate Forum Foundation or any other person or associated institution involved in the making and distribution of the video.