Conjectured improved Junta approximation for low-influence Boolean functions

At least 8 years old · documented by

Let f ⁣:{0,1}n→{0,1}f\colon\left\{0,1\right\}^{n}\to\left\{0,1\right\} be a Boolean function, write μ=E[f]\mu=\mathbb{E}[f], and let I(f)I(f) denote its total influence. A function gg is a Junta if it depends on only a bounded number of coordinates. Improved Junta approximation conjecture. For any M,ϵ>0M,\epsilon>0, any function ff satisfying

I(f)≤2μ(log⁡(1/μ)+M)I(f)\le 2\mu(\log(1/\mu)+M)

can be ϵμ\epsilon\mu-approximated by a function gg that depends on at most O(log⁡(1/μ)⋅2M/ϵ)O(\log(1/\mu)\cdot 2^{M/\epsilon}) coordinates. The paper presents this as a reasonable conjecture in its open-problems section; it would strengthen the paper's Junta approximation result for functions whose influence is close to the minimum.

References

Primary source

Nathan Keller and Noam Lifshitz, “Approximation of biased Boolean functions of small total influence by DNF's”, arXiv:1703.10116 (2017).

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.