caa a22 4500 469068892 CHVBK 20180323132915.0 cr unu---uuuuu 170328e19920201xx s 000 0 eng 10.1007/BF02808010 doi (NATIONALLICENCE)springer-10.1007/BF02808010 The influence of variables in product spaces [Elektronische Daten] [Jean Bourgain, Jeff Kahn, Gil Kalai, Yitzhak Katznelson, Nathan Linial] LetX be a probability space and letf: X n → {0, 1} be a measurable map. Define the influence of thek-th variable onf, denoted byI f (k), as follows: Foru=(u 1,u 2, ,u n−1) ∈X n−1 consider the setl k (u)={(u 1,u 2,...,u k−1,t,u k , ,u n−1):t ∈X}. $$I_f (k) = \Pr (u \in X^{n - 1} :f is not constant on l_k (u)).$$ More generally, forS a subset of [n]={1,...,n} let the influence ofS onf, denoted byI f (S), be the probability that assigning values to the variables not inS at random, the value off is undetermined. Theorem 1:There is an absolute constant c 1 so that for every function f: X n → {0, 1},with Pr(f −1(1))=p≤1/2,there is a variable k so that $$I_f (k) \geqslant c_1 p\frac{{\log n}}{n}.$$ Theorem 2:For every f: X n → {0, 1},with Prob(f=1)=1/2, and every ε>0,there is S ⊂ [n], |S|=c 2(ε)n/logn so that I f (S)≥1−ε. These extend previous results by Kahn, Kalai and Linial for Boolean functions, i.e., the caseX={0, 1}. Hebrew University, 1992 Bourgain Jean Département de Mathématiques, IHES, 35 route de Chartres, Bures-sur-Yvette, France aut Kahn Jeff Department of Mathematics, Rutgers University, 08903, New Brunswick, NJ, USA aut Kalai Gil Landau Center for Research in Mathematical Analysis Institute of Mathematics and Computer Science, The Hebrew University of Jerusalem, 91904, Jerusalem, Israel aut Katznelson Yitzhak Department of Mathematics, Stanford University, 94305, Stanford, CA, USA aut Linial Nathan Landau Center for Research in Mathematical Analysis Institute of Mathematics and Computer Science, The Hebrew University of Jerusalem, 91904, Jerusalem, Israel aut Israel Journal of Mathematics Springer-Verlag 77/1-2(1992-02-01), 55-64 0021-2172 77:1-2<55 1992 77 11856 https://doi.org/10.1007/BF02808010 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02808010 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Bourgain Jean Département de Mathématiques, IHES, 35 route de Chartres, Bures-sur-Yvette, France aut NATIONALLICENCE 700 1- Kahn Jeff Department of Mathematics, Rutgers University, 08903, New Brunswick, NJ, USA aut NATIONALLICENCE 700 1- Kalai Gil Landau Center for Research in Mathematical Analysis Institute of Mathematics and Computer Science, The Hebrew University of Jerusalem, 91904, Jerusalem, Israel aut NATIONALLICENCE 700 1- Katznelson Yitzhak Department of Mathematics, Stanford University, 94305, Stanford, CA, USA aut NATIONALLICENCE 700 1- Linial Nathan Landau Center for Research in Mathematical Analysis Institute of Mathematics and Computer Science, The Hebrew University of Jerusalem, 91904, Jerusalem, Israel aut NATIONALLICENCE 773 0- Israel Journal of Mathematics Springer-Verlag 77/1-2(1992-02-01), 55-64 0021-2172 77:1-2<55 1992 77 11856 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer