2024/03/29 by Tomasz Przybyłowski, Przybyłowski, Tomasz · 1 citation
Engineering · #Advanced Control Systems Optimization
paper · pdf · doi:10.48550/arxiv.2404.00084
Consider a Boolean function f on the n-dimensional hypercube, and a set of variables (indexed by) S ⊂ \1,2,…,n\. The coalition influence of the variables S on a function f is the probability that after a random assignment of variables not in S, the value of f is undetermined. In this paper, we study a complementary notion, which we call the joint influence: the probability that, after a random assignment of variables not in S, the value of f is dependent on all variables in S. We show that for an arbitrary fixed d, every Boolean function f on n variables admits a d-set of joint influence at least \tfrac110 W≥ d(f) ((log n)/(n))d, where W≥ d(f) is the Fourier weight of f at degrees at least d. This result is a direct generalisation of the Kahn-Kalai-Linial theorem. Further, we give an example demonstrating essential sharpness of the above bound. In our study of the joint influence we consider another notion of multi-bit influence recently introduced by Tal.