Boolean functions with small spectral norm, revisited

Author: 

Sanders, T

Publication Date: 

16 May 2018

Journal: 

Mathematical Proceedings of the Cambridge Philosophical Society

Last Updated: 

2020-07-28T05:09:28.55+01:00

Issue: 

2

Volume: 

167

DOI: 

10.1017/S030500411800035X

page: 

335-344

abstract: 

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 .

Symplectic id: 

835378

Submitted to ORA: 

Submitted

Publication Type: 

Journal Article