# Theory Seminar: Properties and Applications of Boolean Function Composition

- Speaker:
- Avishay Tal (Weizmann Institute of Science)
- Date:
- Wednesday, 3.4.2013, 12:30
- Place:
- Taub 201

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 .