Kindler–Safra conjecture for balanced Boolean functions on the symmetric group
Kindler–Safra conjecture for balanced Boolean functions on the symmetric group
Let be the symmetric group, and let be a Boolean function. Say that is -close to degree if its distance from the space of degree- functions is at most , where degree is defined using polynomial expressions in the variables . Let denote the uniform expectation of on . Kindler–Safra conjecture. If is -close to degree and
then is -close to a Boolean degree- 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.