文章基本信息

标题：Decision Trees and Influence: an Inductive Proof of the OSSS Inequality
本地全文：下载
作者：Homin K. Lee
期刊名称：Theory of Computing
印刷版ISSN：1557-2862
电子版ISSN：1557-2862
出版年度：2010
卷号：6
页码：81-84
DOI：10.4086/toc.2010.v006a004
语种：English
出版社：University of Chicago
摘要：We give a simple proof of the OSSS inequality (O’Donnell, Saks, Schramm, Servedio, FOCS 2005). The inequality states that for any decision tree $T$ calculating a Boolean function $f:\zo^n\rightarrow \oo$, we have $\Var[f] \leq \sum_i \delta_i(T)\Inf_i(f)$, where $\delta_i(T)$ is the probability that the input variable $x_i$ is read by $T$ and $\Inf_i(f)$ is the influence of the $i$th variable on $f$.
关键词：probability; computational complexity; decision trees