Squared-influence logarithmic lower bound

ID: squared-influence-logarithmic-lower-bound

For a zero-one Boolean function of mean , the displayed bound holds for sufficiently large , uniformly in . If it failed, put , and split its nonconstant Fourier weight at level . The total influence bound puts at most above that level. The hypercontractive weighted influence bound with puts only below it: the conversion factor stays bounded, while . This contradicts total nonconstant weight .

New to topics? Read the docs here!