Kindler–Safra conjecture for balanced Boolean functions on the symmetric group

Let SnS_n be the symmetric group, and let f ⁣:Sn{0,1}f\colon S_n\to\{0,1\} be a Boolean function. Say that ff is ϵ\epsilon-close to degree dd if its distance from the space of degree-dd functions is at most ϵ\epsilon, where degree is defined using polynomial expressions in the variables xi,jx_{i,j}. Let E[f]\mathbb{E}[f] denote the uniform expectation of ff on SnS_n. Kindler–Safra conjecture. If ff is ϵ\epsilon-close to degree dd and

13E[f]23,\frac{1}{3}\leq \mathbb{E}[f]\leq \frac{2}{3},

then ff is O(ϵ)O(\epsilon)-close to a Boolean degree-dd function. This is the conjectured extension of the Kindler–Safra theorem to the symmetric group in the balanced case; the corresponding result is known on several other domains, but the symmetric-group version is presented here as a conjecture.

Sources & referencesView supporting material

Primary source

Yuval Filmus, “Boolean functions on S_n which are nearly linear”, arXiv:2107.07833 (2021).

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.