TY - GEN

T1 - PROBABILISTIC BOOLEAN DECISION TREES AND THE COMPLEXITY OF EVALUATING GAME TREES.

AU - Saks, Michael

AU - Wigderson, Avi

PY - 1986

Y1 - 1986

N2 - The power of randomness in the Boolean decision-tree model is studied, and separation results among three complexity measures are proved. The results are obtained using general and efficient methods for computing upper and lower bounds on the probabilistic complexity of evaluating Boolean formulas in which every variable appears exactly once (AND/OR tree with distinct leaves). These bounds are shown to be exactly tight for interesting families of such tree functions. The results are then applied to the complexity of evaluating game trees. These trees are similar to Boolean tree functions, except that input variables (leaves) may take values from a large set (of valuations to game positions) and the AND/OR nodes are replaced by MIN/MAX nodes. The best known algorithm for this problem is the alpha-beta pruning method. A randomized variant of alpha-beta pruning is analyzed, and it is shown that it is considerably faster than the deterministic variant in the case and optimal for uniform trees.

AB - The power of randomness in the Boolean decision-tree model is studied, and separation results among three complexity measures are proved. The results are obtained using general and efficient methods for computing upper and lower bounds on the probabilistic complexity of evaluating Boolean formulas in which every variable appears exactly once (AND/OR tree with distinct leaves). These bounds are shown to be exactly tight for interesting families of such tree functions. The results are then applied to the complexity of evaluating game trees. These trees are similar to Boolean tree functions, except that input variables (leaves) may take values from a large set (of valuations to game positions) and the AND/OR nodes are replaced by MIN/MAX nodes. The best known algorithm for this problem is the alpha-beta pruning method. A randomized variant of alpha-beta pruning is analyzed, and it is shown that it is considerably faster than the deterministic variant in the case and optimal for uniform trees.

UR - http://www.scopus.com/inward/record.url?scp=0022863767&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0022863767&partnerID=8YFLogxK

U2 - 10.1109/sfcs.1986.44

DO - 10.1109/sfcs.1986.44

M3 - Conference contribution

AN - SCOPUS:0022863767

SN - 0818607408

SN - 9780818607400

T3 - Annual Symposium on Foundations of Computer Science (Proceedings)

SP - 29

EP - 38

BT - Annual Symposium on Foundations of Computer Science (Proceedings)

PB - IEEE

ER -