[hal-01184382] Monotone Boolean Functions with s Zeros Farthest from Threshold Functions

Let T_t denote the t-threshold function on the n-cube: T_t(x) = 1 if |\i : x_i=1\| ≥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∈\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].

from HAL : Dernières publications http://ift.tt/1DQQOp0