Approximate spectral norm conjecture for symmetric Boolean functions

For a Boolean function f:{0,1}n{±1}f:\{0,1\}^n\to\{\pm1\}, let f^1,ϵ\|\widehat f\|_{1,\epsilon} be the smallest spectral norm of a function gg satisfying

fgϵ.\|f-g\|_\infty\leq\epsilon.

The function ff is symmetric when its value depends only on the Hamming weight of the input. Approximate spectral norm conjecture. For every symmetric function ff,

logf^1=Θ(logf^1,1/3),\log \|\widehat f\|_1=\Theta^*(\log \|\widehat f\|_{1,1/3}),

where Θ\Theta^* suppresses O(logn)O(\log n) 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

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.