The seminal result of Kahn, Kalai and Linial shows that a coalition of O ( n log n ) players can bias the outcome of *any* Boolean function 0 1 n 0 1 with respect to the uniform measure. We extend their result to arbitrary product measures on 0 1 n , by combining their argument with a completely different argument that handles very biased coordinates.

We view this result as a step towards proving a conjecture of Friedgut, which states that Boolean functions on the continuous cube [0 1 ] n (or, equivalently, on 1 n n ) can be biased using coalitions of o ( n ) players. This is the first step taken in this direction since Friedgut proposed the conjecture in 2004.

Russell, Saks and Zuckerman extended the result of Kahn, Kalai and Linial to multi-round protocols, showing that when the number of rounds is o ( log n ) , a coalition of o ( n ) players can bias the outcome with respect to the uniform measure. We extend this result as well to arbitrary product measures on 0 1 n .

The argument of Russell et al.\ relies on the fact that a coalition of o ( n ) players can boost the expectation of any Boolean function from to 1 − with respect to the uniform measure. This fails for general product distributions, as the example of the AND function with respect to 1 − 1 n shows. Instead, we use a novel boosting argument alongside a generalization of our first result to arbitrary finite ranges.