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

Michael Saks, Avi Wigderson

Research output: Chapter in Book/Report/Conference proceedingConference contribution

140 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherIEEE
Pages29-38
Number of pages10
ISBN (Print)0818607408, 9780818607400
DOIs
StatePublished - 1986
Externally publishedYes

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'PROBABILISTIC BOOLEAN DECISION TREES AND THE COMPLEXITY OF EVALUATING GAME TREES.'. Together they form a unique fingerprint.

Cite this