The Taub Faculty of Computer Science Events and Talks

For Boolean functions f : {0, 1} → {0, 1} and g : {0, 1}m → {0, 1}, the function composition of f and g denoted by f ◦ g : {0, 1}nm → {0, 1} is the value of f on n inputs, each of them is the calculation of g on a distinct set of m Boolean variables. Motivated by previous works that achieved some of the best separations between complexity measures such as sensitivity, block-sensitivity, degree, certi?cate complexity and decision tree complexity we show that most of these complexity measures behave multiplicatively under composition. We use this multiplicative behavior to establish several applications.

First, we give a negative answer for Adam Kalai's question from [MOS04]: "Is it true that every Boolean function f : {0, 1}n → {0, 1} with degree as a polynomial over the reals (denoted by deg(f )) at most n/3, has a restriction ?xing 2n/3 of its variables under which f becomes a parity function?"; This question was motivated by the problem of learning juntas as it suggests a simple algorithm, faster than that of Mossel et al. We give a counterexample for the question using composition of functions strongly related to the Walsh-Hadamard code. In fact, we show that for every constants ϵ, δ > 0 there are (in?nitely many) Boolean functions f : {0, 1}n → {0, 1} such that deg(f ) ≤ ϵ · n and under any restriction ?xing less than (1 − δ) · n variables, f does not become a parity function.

Second, we show that for composition, the block sensitivity (denoted by bs) property has an unusual behavior - namely that bs(f ◦ g) can be larger than bs(f ) · bs(g). We show that the ratio between these two has a strong connection to the integrality gap of the Set Packing problem. In addition, we obtain the best known separation between block-sensitivity and certi?cate complexity (denoted by C) giving in?nitely many functions f such that C(f ) ≥ bs(f )log(26)/ log(17) = bs(f )1.149... . Last, we present a factor 2 improvement of a result by Nisan and Szegedy [NS94], by showing that for all Boolean functions bs(f ) ≤ deg(f )2 .