DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

Monotone Boolean Functions with s Zeros Farthest from Threshold Functions

Kazuyuki Amano, Jun Tarui


Let Tt denote the t-threshold function on the n-cube: Tt(x) = 1 if |{i : xi=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,Tt)? We show that the following monotone function ps maximizes the distance: For x∈{0,1}n, ps(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=⌈n/2 ⌉ and s=2n-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].

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional