Conjectured improved Junta approximation for low-influence Boolean functions

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.

Sources & referencesView supporting material

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.