Wegener's monotone address

Definition

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

$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}.$

In words, if the first $k$ input bits have Hamming weight less than $k/2$, the function's value is $-1$. If the Hamming weight is greater than $k/2$, the value is $+1$. And if the Hamming weight is exactly $k/2$, then the $n$ 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 $f$ is $k/2 + 1$.
• The function $f$ has sensitivity $\frac{1}{2}\log n + \frac{1}{4} \log\log n + O(1)$.