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
      0 references
      7 September 2004
      0 references
      influence
      0 references
      Boolean function
      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

      Identifiers