The sensitivity-weighted variable bound for Boolean functions
The sensitivity-weighted variable bound for Boolean functions
Let be a Boolean function. Write for its number of relevant variables, for its sensitivity, and define
Here indicates whether variable is relevant and is its individual sensitivity.
Sensitivity-weighted variable conjecture. For every Boolean function ,
More strongly,
This would improve Simon's theorem by giving a constant bound on the sensitivity-weighted quantity and, consequently, the stated bound on the number of relevant variables. The paper presents this as an open conjecture and gives evidence for it, but no resolution is supplied.
Sources & referencesView supporting material
Primary source
Jake Wellens, “Relationships between the number of inputs and other complexity measures of Boolean functions”, arXiv:2005.00566 (2022).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.