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!