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 <>
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


  • HAL Id : hal-01184382, version 1



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. ⟨hal-01184382⟩



Record views


Files downloads