Exact maximal average sensitivity of nested canalizing functions

Let ff be a Boolean nested canalizing function in nn variables. Write its layer parameters as r,k1,,krr,k_1,\ldots,k_r, where rr is the layer number, and let sfs^f denote its average sensitivity.

Exact maximal-average-sensitivity conjecture. The maximal value of sfs^f is

sf=433+(1)n3×2n.s^f=\frac{4}{3}-\frac{3+(-1)^n}{3\times 2^n}.

It is attained when r=n1r=n-1, k1==kn2=1k_1=\cdots=k_{n-2}=1, and kn1=2k_{n-1}=2. When nn is even, it is also attained for n4n\geq 4 with r=n2r=n-2, k1==kn3=1k_1=\cdots=k_{n-3}=1, kn2=3k_{n-2}=3, or for n6n\geq 6 with r=n2r=\frac n2, k1=1k_1=1, k2==kn21=2k_2=\cdots=k_{\frac n2-1}=2, and kn2=3k_{\frac n2}=3.

The claim is based on numerical calculations, an explicit average-sensitivity formula, and several evaluated parameter families. It refines the broader conjecture that maximal layer number gives maximal average sensitivity; its general optimality remains open.

Sources & referencesView supporting material

Primary source

Yuan Li, John O. Adeyeye, David Murrugarra, Boris Aguilar and Reinhard Laubenbacher, “Boolean nested canalizing functions: a comprehensive analysis”, arXiv:1204.5203 (2013).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.