Low-influence approximation conjecture for Boolean functions

For a Boolean function ff, define its total influence by

I(f)=Sf^(S)2S.I(f)=\sum_S\widehat f(S)^2|S|.

A Boolean function gg ϵ\epsilon-approximates ff when E(fg)2ϵ\mathbb E(f-g)^2\le\epsilon. Low-influence approximation conjecture. For some absolute constant CC, every Boolean function ff can be 0.010.01-approximated by a circuit of depth dd and size MM satisfying

(logM)CdI(f).(\log M)^{Cd}\le I(f).

This is proposed as a reverse-Håstad-type statement and remains open in the supplied text.

Sources & referencesView supporting material

Primary source

Gil Kalai, “Three Puzzles on Mathematics, Computation, and Games”, arXiv:1801.02602 (2018).

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.