文章基本信息
- 标题：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
- 出版社：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 : {0,1} n → {-1,1}, we have Var [ f ] ≤ ∑i δi ( T ) Inf i ( f ) , where δi ( T ) is the probability that the input variable xi is read by T and Inf i ( f ) is the influence of the i -th variable on f .
- 关键词：probability, computational complexity, decision trees
