Geodesic
Relationships between the number of inputs and other complexity measures of Boolean functions
Discrete analysis (2022)

Voir la notice de l'article provenant de la source Scholastica

arXiv
We generalize and extend the ideas in a recent paper of Chiarelli, Hatami and Saks to prove new bounds on the number of relevant variables for boolean functions in terms of a variety of complexity measures. Our approach unifies and refines all previously known bounds of this type. We also improve Nisan and Szegedy's well-known block sensitivity vs. degree inequality by a constant factor, thereby improving Huang's recent proof of the sensitivity conjecture by the same constant.
Publié le : 
Jake Wellens. Relationships between the number of inputs and other complexity measures of Boolean functions. Discrete analysis (2022). http://geodesic.mathdoc.fr/item/DAS_2022_a0/
@article{DAS_2022_a0,
     author = {Jake Wellens},
     title = {Relationships between the number of inputs and other complexity measures of {Boolean} functions},
     journal = {Discrete analysis},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DAS_2022_a0/}
}
TY  - JOUR
AU  - Jake Wellens
TI  - Relationships between the number of inputs and other complexity measures of Boolean functions
JO  - Discrete analysis
PY  - 2022
UR  - http://geodesic.mathdoc.fr/item/DAS_2022_a0/
LA  - en
ID  - DAS_2022_a0
ER  - 
%0 Journal Article
%A Jake Wellens
%T Relationships between the number of inputs and other complexity measures of Boolean functions
%J Discrete analysis
%D 2022
%U http://geodesic.mathdoc.fr/item/DAS_2022_a0/
%G en
%F DAS_2022_a0