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].