Choose maximal such that for the displayed , and take the OR of AND blocks of size , ignoring unused coordinates. Its failure probability is , between one quarter and three quarters. Active coordinates have influence and unused ones have zero influence. Maximality gives ; for , , so every influence is below . The construction is therefore a quite fair Boolean function with small influences for every . The logarithmic bound cannot hold at , where every quite fair function has influence one.

Articles by others on the same topic (0)

There are currently no matching articles.