Maximum-influence logarithmic lower bound

ID: maximum-influence-logarithmic-lower-bound

For a zero-one Boolean function on the unbiased Boolean hypercube with flip-probability influences , the displayed bound holds for sufficiently small . If it fails, write . The total influence identity puts at least half the nonconstant Fourier weight on levels . The hypercontractive weighted influence bound at then gives . Its upper bound contradicts .

New to topics? Read the docs here!