Kindler–Safra conjecture for balanced Boolean functions on the symmetric group
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.