Boolean functions with small spectral norm, revisited
We show that if f is a Boolean function on Fn 2 with spectral norm at most M then there is some L exp(M3+o(1) ) and subspaces V1,..., VL such that f = i ±1Vi .
| Main Author: | |
|---|---|
| Format: | Journal article |
| Published: |
Cambridge University Press
2018
|