 Every decision tree has an influential variable by Ryan O'Donnell and others

By Ryan O'Donnell, Michael Saks, Oded Schramm, Rocco A. Servedio.

Publisher: arXiv (repository).

Online text: arxiv.org/pdf/cs/0508071

arXiv version 1 submitted on 16 August 2005. The retrieved PDF typesetting date is not used as the publication year.

Cited passages: O'Donnell, Saks, Schramm and Servedio, Every decision tree has an influential variable, section 1.2, p. 2: δ_i(T) and Δ(T); section 3.1, p. 6: distinct coordinates along each root–leaf path; O'Donnell, Saks, Schramm and Servedio, Every decision tree has an influential variable, sections 1.1–1.2, pp. 1–2: worst-input expected randomized cost R(f) versus input-distribution average Δ(T).