Computer Science/Discrete Mathematics Seminar I

The seminal result of Kahn, Kalai and Linial implies that a coalition of a small number of players can bias the outcome of a Boolean function with respect to the uniform measure. We extend this result to arbitrary product measures, 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 (or, equivalently, on large alphabet) can be biased using small coalitions of players towards one of the two outcomes. This talk is based on a joint work with Yuval Filmus, Lianna Hambardzumyan, Pooya Hatami, and David Zuckerman.