ECCC-Report TR12-163https://eccc.weizmann.ac.il/report/2012/163Comments and Revisions published for TR12-163en-usSat, 24 Nov 2012 19:34:22 +0200
Paper TR12-163
| Properties and Applications of Boolean Function Composition |
Avishay Tal
https://eccc.weizmann.ac.il/report/2012/163For Boolean functions $f:\{0,1\}^n \to \{0,1\}$ and $g:\{0,1\}^m \to \{0,1\}$, the function composition of $f$ and $g$ denoted by $f\circ g : \{0,1\}^{nm} \to \{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, certificate 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\to\{0,1\}$ with degree as a polynomial over the reals (denoted by $\deg(f)$) at most $n/3$, has a restriction fixing $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 $\epsilon,\delta>0$ there are (infinitely many) Boolean functions $f: \{0,1\}^n \to \{0,1\}$ such that $\deg(f) \le \epsilon \cdot n$ and under any restriction fixing less than $(1-\delta) \cdot n$ variables, $f$ does not become a parity function.
Second, we show that for composition, the block sensitivity (denoted by $\mathrm{bs}$) property has an unusual behavior - namely that $\mathrm{bs}(f\circ g)$ can be larger than ${\mathrm{bs}}(f) \cdot {\mathrm{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 certificate complexity (denoted by ${\mathrm{C}}$) giving infinitely many functions $f$ such that ${\mathrm{C}}(f) \ge {\mathrm{bs}}(f)^{\log(26)/\log(17)} = {\mathrm{bs}}(f)^{1.149\ldots}$.
Last, we present a factor $2$ improvement of a result by Nisan and Szegedy [NS94], by showing that for all Boolean functions ${\mathrm{bs}}(f) \le \deg(f)^2$.
Sat, 24 Nov 2012 19:34:22 +0200https://eccc.weizmann.ac.il/report/2012/163