Wegener's monotone address

Definition

For even [math]k[/math], let [math]n = k + \binom{k}{2}[/math]. Wegner's monotone address function [math]f:\{-1,1\}^{n} \to \{-1,1\}[/math] is defined as follows. Let [math]A = \{S \subseteq \{1,\ldots,k \} : |S| = k/2 \}[/math] be the subsets of [math]1\ldots k[/math] of size [math]k/2[/math], and let [math]\alpha[/math] be an arbitrary one-to-one mapping from [math]A[/math] to [math]\{1,\ldots, \binom{k}{2} \}[/math]. Denote by [math]h(x)[/math] the Hamming weight of [math]x[/math], i.e the number of ones in the vector [math]x[/math]. Then [math]f(x)[/math] is defined as follows:

[math]f(x_1,\ldots,x_k,y_1,\ldots,y_{\binom{k}{2}}) = \begin{cases} -1, & if ~ h(x_1,\ldots,x_k) \lt k / 2 \\ +1 & if ~ h(x_1,\ldots,x_k) \gt k / 2 \\ y_{\alpha(x_1,\ldots,x_k)} & if ~ h(x_1,\ldots,x_k) = k / 2 \end{cases}. [/math]

In words, if the first [math]k[/math] input bits have Hamming weight less than [math]k/2[/math], the function's value is [math]-1[/math]. If the Hamming weight is greater than [math]k/2[/math], the value is [math]+1[/math]. And if the Hamming weight is exactly [math]k/2[/math], then the [math]n[/math] bits serve to select an arbitrary bit from the rest of the input, similar to the address function.

Properties

• As the name suggests, the function is monotone.
• The critical complexity of [math]f[/math] is [math]k/2 + 1[/math].
• The function [math]f[/math] has sensitivity [math]\frac{1}{2}\log n + \frac{1}{4} \log\log n + O(1)[/math].