Influences in Product Spaces: KKL and BKKKL Revisited (Q4812337)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2097584
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Influences in Product Spaces: KKL and BKKKL Revisited |
scientific article; zbMATH DE number 2097584 |
Statements
Influences in Product Spaces: KKL and BKKKL Revisited (English)
0 references
7 September 2004
0 references
influence
0 references
Boolean function
0 references
0.7650833
0 references
0.7333137
0 references
0.6925319
0 references
0 references
0 references
0.69001275
0 references
Let \(X\) be a set endowed with a \(\sigma\)-algebra and a probability measure on that \(\sigma\)-algebra. Let \(X^n\) be the product space endowed with the corresponding product probability \(P\). Let \(f:X^n\to\{0,1\}\) be a measurable function. For \(j=1,\dots,n\), the quantity \[ I_f(j)=P(\{(x_1,\dots,x_n)\in X^n: f\text{ is not constant on }\{(y_1,\dots,y_n)\in X^n:y_i=x_i\text{ for }i \neq j\}\}) \] is called the influence of the \(j\)th variable on \(f\). The author revisits the following theorems. Theorem 1. Let \(P\) be the uniform probability measure on \(\{0,1\}^n\), and let \(f:\{0,1\}^n\to\{0,1\}\) be such that \(P(\{f=1\})=p\). Then there exists a constant \(c>0\) so that \(\sum_{j=1}^n I_{f}(j)\geq c(\log \delta)p(1-p)\) whenever \(I_f(j) \leq\delta\), \(1 \leq j \leq n\). Theorem 2. Let \(P\) be the uniform probability measure on \([0,1]^n\), and let \(f:[0,1]^n\to\{0,1\}\) be such that \(P(\{f=1\})=p\). Then there exists a constant \(c>0\) so that \(I_f(k)>c \frac{\log n}{n} p(1-p)\) for some \(k\). Theorem 1 is a modification of a result obtained by \textit{J. Kahn, G. Kalai} and \textit{N. Linial} [in: 29th Ann. Symp. Foundations of Comp. Sci. 68--80 (1988)], and Theorem 2 is due to \textit{J. Bourgain, J. Kahn, G. Kalai, Y. Katznelson} and \textit{N. Linial} [Isr. J. Math. 77, 55--64 (1992; Zbl 0771.60002)]. The author claims that Theorem 1 implies Theorem 2 by discretizing the continuous cube. The paper is mostly descriptive. It contains seven conjectures.
0 references