Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2404.00084 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908769977368576 |
|---|---|
| author | Przybyłowski, Tomasz |
| author_facet | Przybyłowski, Tomasz |
| contents | Consider a Boolean function f on the n-dimensional hypercube, and a set of variables (indexed by) $S \subset \{1,2,\ldots,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 $\tfrac{1}{10} W^{\geq d}(f) (\frac{\log n}{n})^d$, where $W^{\geq 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_00084 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | KKL theorem for the influence of a set of variables Przybyłowski, Tomasz Combinatorics Discrete Mathematics Probability 42C10, 60E15, 68R01 Consider a Boolean function f on the n-dimensional hypercube, and a set of variables (indexed by) $S \subset \{1,2,\ldots,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 $\tfrac{1}{10} W^{\geq d}(f) (\frac{\log n}{n})^d$, where $W^{\geq 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. |
| title | KKL theorem for the influence of a set of variables |
| topic | Combinatorics Discrete Mathematics Probability 42C10, 60E15, 68R01 |
| url | https://arxiv.org/abs/2404.00084 |