Boolean functions with small spectral norm
classification
🧮 math.CA
math.CO
keywords
booleanfunctionsnormspectralabsolutecoefficientscombinationexpressed
read the original abstract
Suppose that f is a boolean function from F_2^n to {0,1} with spectral norm (that is the sum of the absolute values of its Fourier coefficients) at most M. We show that f may be expressed as +/- 1 combination of at most 2^(2^(O(M^4))) indicator functions of subgroups of F_2^n.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.