Approximate spectral norm conjecture for symmetric Boolean functions
Approximate spectral norm conjecture for symmetric Boolean functions
For a Boolean function , let be the smallest spectral norm of a function satisfying
The function is symmetric when its value depends only on the Hamming weight of the input. Approximate spectral norm conjecture. For every symmetric function ,
where suppresses factors. Extending the spectral-norm theorem to approximate spectral norm would have implications for learning and complexity measures; the conjectured comparison is presented as an open next step.
Sources & referencesView supporting material
Primary source
Anil Ada, Omar Fawzi and Hamed Hatami, “Spectral Norm of Symmetric Functions”, arXiv:1205.5282 (2012).
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.