2009/05/26 by Nathan Keller, Keller, Nathan · 2 citations
Computer Science · Mathematics · #05D40 #60C05 #Advanced Algebra and Logic #Advanced Topology and Set Theory #Algebra over a field #Assertion #Boolean function #Combinatorics #Combinatorics (math.CO) #Complete Boolean algebra #Computer science #Cube (algebra) #Discrete mathematics #FOS: Mathematics #Generalization #Mathematics #Probability (math.PR) #Product (mathematics) #Product term #Pure mathematics #Two-element Boolean algebra #math.CO #math.PR #msc:05D40 #msc:60C05 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.0905.4216
published in arXiv (Cornell University) (Cornell University) · 21 pages, 1 figure, submitted for publication
arxiv created 2009/05/26 · openalex publication_date 2009/05/26 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
In this paper we consider the influences of variables on Boolean functions in general product spaces. Unlike the case of functions on the discrete cube where there is a clear definition of influence, in the general case at least three definitions were presented in different papers. We propose a family of definitions for the influence, that contains all the known definitions, as well as other natural definitions, as special cases. We prove a generalization of the BKKKL theorem, which is tight in terms of the definition of influence used in the assertion, and use it to generalize several known results on influences in general product spaces.