HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Monotone Boolean Functions with s Zeros Farthest from Threshold Functions

Abstract : Let $T_t$ denote the $t$-threshold function on the $n$-cube: $T_t(x) = 1$ if $|\{i : x_i=1\}| \geq t$, and $0$ otherwise. Define the distance between Boolean functions $g$ and $h$, $d(g,h)$, to be the number of points on which $g$ and $h$ disagree. We consider the following extremal problem: Over a monotone Boolean function $g$ on the $n$-cube with $s$ zeros, what is the maximum of $d(g,T_t)$? We show that the following monotone function $p_s$ maximizes the distance: For $x \in \{0,1\}^n$, $p_s(x)=0$ if and only if $N(x) < s$, where $N(x)$ is the integer whose $n$-bit binary representation is $x$. Our result generalizes the previous work for the case $t=\lceil n/2 \rceil$ and $s=2^{n-1}$ by Blum, Burch, and Langford [BBL98-FOCS98], who considered the problem to analyze the behavior of a learning algorithm for monotone Boolean functions, and the previous work for the same $t$ and $s$ by Amano and Maruoka [AM02-ALT02].
Complete list of metadata

Cited literature [2 references]  Display  Hide  Download

Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Friday, August 14, 2015 - 11:38:44 AM
Last modification on : Thursday, May 11, 2017 - 1:02:53 AM
Long-term archiving on: : Sunday, November 15, 2015 - 11:04:29 AM


Publisher files allowed on an open archive




Kazuyuki Amano, Jun Tarui. Monotone Boolean Functions with s Zeros Farthest from Threshold Functions. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.11-16, ⟨10.46298/dmtcs.3425⟩. ⟨hal-01184382⟩



Record views


Files downloads