= Tribes function
A tribes function is an OR of AND blocks: partition $mw$ coordinates into $m$ blocks of size $w$, and let $f=1$ when at least one block consists entirely of ones. For <independent random variables> with each bit uniform, $\mathbb P(f=0)=(1-2^{-w})^m$. The <influence of a variable> is $2^{-(w-1)}(1-2^{-w})^{m-1}$, because every other bit in its block must be one and every other block must fail. Taking $m$ approximately $(\log2)2^w$ keeps both output probabilities bounded away from zero and gives influences of order $\log(mw)/(mw)$. This shows the order in the <Kahn-Kalai-Linial theorem> is sharp.
Back to article page
