Boolean functions whose Fourier transform is concentrated on pairwise disjoint subsets of the input

Aviad Rubinstein, Muli Safra

We consider Boolean functions f:{-1,1}^n->{-1,1} that are close to a sum of independent functions on mutually exclusive subsets of the variables. We prove that any such function is…