On the Parallel Evaluation of Boolean Expressions
Amnon Barak, Eliahu Shamir · SIAM Journal on Computing · 1976
A bound for the number of steps that are required to evaluate Boolean expressions is obtained. It is shown that any Boolean expression of n distinct variables may be evaluated in $2\log _2 n - 1$ steps if sufficiently many processors are available.