Decision Trees and Influence: an Inductive Proof of the OSSS Inequality
by Homin K. Lee
Theory of Computing, Volume 6(4), pp. 81-84, 2010
Bibliography with links to cited articles
[1] Michael Ben-Or and Nathan Linial: Collective coin flipping. In S. Micali, editor, Randomness and Computation, pp. 91–115. Acad. Press, 1989. Preliminary version in Proc. FOCS’85.
[2] Bradley Efron and Charles Stein: The jackknife estimate of variance. Ann. Statist., 9:586–596, 1981. [doi:10.1214/aos/1176345462].
[3] Ryan O’Donnell, Michael Saks, Oded Schramm, and Rocco A. Servedio: Every decision tree has an influential variable. In Proc. 46th FOCS, pp. 31–39. IEEE Computer Soc., 2005. [doi:10.1109/SFCS.2005.34].
[4] Ryan O’Donnell and Rocco A. Servedio: Learning monotone decision trees in polynomial time. SIAM J. Comput., 37(3):827–844, 2007. Preliminary version in Proc. of CCC’06. [doi:10.1137/060669309].
[5] J. Michael Steele: An Efron-Stein inequality for nonsymmetric statistics. Ann. Statist., 14:753–758, 1986. [doi:10.1214/aos/1176349952].