KKL theorem for the influence of a set of variables
<|reference_start|>KKL theorem for the influence of a set of variables: We study the notion of the influence of a set of variables on a Boolean function, which was recently introduced by Tal. We show that for an arbitrary fixed $d$, every Boolean function $f$ on $n$ variables admits a $d$-set of influence at least $\frac{1}{10} \mathbf{W}^{\geq d}(f) (\frac{\log n}{n})^d$, which is a direct generalisation of the Kahn-Kalai-Linial theorem. We give an example demonstrating essential sharpness of this result. Further, we generalise a related theorem of Oleszkiewicz regarding influences of pairs of variables.<|reference_end|>
@article{przybyłowski2024kkl,
    title={KKL theorem for the influence of a set of variables},
    author={Tomasz Przyby{l}owski},
    journal={arXiv preprint arXiv:2404.00084},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.00084},
    primaryClass={math.CO cs.DM math.PR}
}