Balanced tribes construction with unused coordinates
ID: balanced-tribes-construction-with-unused-coordinates
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.
New to topics? Read the docs here!