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

https://hal.inria.fr/hal-01184382
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

File

dmAE0103.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

49

Files downloads

489