The sensitivity-weighted variable bound for Boolean functions

Let f:{0,1}n{0,1}f:\{0,1\}^n\to\{0,1\} be a Boolean function. Write n(f)n(f) for its number of relevant variables, s(f)s(f) for its sensitivity, and define

S(f):=i[n]δi(f)2sensi(f).S(f):=\sum_{i\in[n]}\frac{\delta_i(f)}{2^{\operatorname{sens}_i(f)}}.

Here δi(f)\delta_i(f) indicates whether variable ii is relevant and sensi(f)\operatorname{sens}_i(f) is its individual sensitivity.

Sensitivity-weighted variable conjecture. For every Boolean function ff,

n(f)4s(f).n(f)\lesssim 4^{s(f)}.

More strongly,

S(f)1.S(f)\lesssim 1.

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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.