A Lower Bound on the Constant in the Fourier Min-Entropy/Influence Conjecture
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913199213772800 |
|---|---|
| author | Biswas, Aniruddha Sarkar, Palash |
| author_facet | Biswas, Aniruddha Sarkar, Palash |
| contents | We describe a new construction of Boolean functions. A specific instance of our construction provides a 30-variable Boolean function having min-entropy/influence ratio to be $128/45 \approx 2.8444$ which is presently the highest known value of this ratio that is achieved by any Boolean function. Correspondingly, $128/45$ is also presently the best known lower bound on the universal constant of the Fourier min-entropy/influence conjecture. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_07713 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | A Lower Bound on the Constant in the Fourier Min-Entropy/Influence Conjecture Biswas, Aniruddha Sarkar, Palash Computational Complexity We describe a new construction of Boolean functions. A specific instance of our construction provides a 30-variable Boolean function having min-entropy/influence ratio to be $128/45 \approx 2.8444$ which is presently the highest known value of this ratio that is achieved by any Boolean function. Correspondingly, $128/45$ is also presently the best known lower bound on the universal constant of the Fourier min-entropy/influence conjecture. |
| title | A Lower Bound on the Constant in the Fourier Min-Entropy/Influence Conjecture |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2212.07713 |