Combinatorics Seminar

When: Sunday, March 29, 10am Where: Schreiber 309 Speaker: Nathan Keller, Hebrew University Title: The influences of variables on Boolean functions in product spaces

Abstract:

Influences of variables on Boolean functions have been extensively studied during the last few decades. This study led to important applications in numerous fields. In this talk we consider the influences of variables on Boolean functions in general product spaces (endowed with a product measure). Unlike the case of the discrete cube where there is a clear definition of influences, in the general case at least three definitions were presented in different papers. We propose a family of definitions for the influences, that contains all the known definitions, as well as other natural definitions, as special cases. We prove that several previously known theorems about influences in the general case, including the BKKKL theorem, can be improved by replacing the notion of influence by a ``weaker'' one. Our work generalizes previous results of BKKKL (Bourgain, Kahn, Kalai, Katznelson, Linial), Talagrand, Friedgut, and Hatami.