Separation and Collapse of Equilibria Inequalities on AND-OR Trees without Shape Constraints

The document discusses the development and analysis of the "chimera" algorithm, which is a key concept in the study of equilibrium values and probabilistic computations for AND-OR trees, and presents results and proofs related to the interdependence among algorithms and probability distributions.

Abstract

Herein, we investigate the randomized complexity, which is the least cost against the worst input, of AND-OR tree computation by imposing various restrictions on the algorithm to find the Boolean value of the root of that tree and no restrictions on the tree shape. When a tree satisfies a certain condition regarding its symmetry, directional algorithms proposed by Saks and Wigderson (1986), special randomized algorithms, are known to achieve the randomized complexity. Furthermore, there is a known example of a tree that is so unbalanced that no directional algorithm achieves the randomized complexity (Vereshchagin 1998). In this study, we aim to identify where deviations arise between the general randomized Boolean decision tree and its special case, directional algorithms. In this paper, we show that for any AND-OR tree, randomized depth-first algorithms, which form a broader class compared with directional algorithms, have the same equilibrium as that of the directional algorithms. Thus, we get the collapse result on equilibria inequalities that holds for an arbitrary AND-OR tree. This implies that there exists a case where even depth-first algorithms cannot be the fastest, leading to the separation result on equilibria inequality. Additionally, a new algorithm is introduced as a key concept for proof of the separation result.

Method

The method of this paper involves investigating the randomized complexity of AND-OR tree computation, focusing on the equilibrium values and probabilistic computations. The study aims to identify deviations between general randomized Boolean decision trees and directional algorithms, and presents results showing the collapse and separation of equilibria inequalities on AND-OR trees without shape constraints. Additionally, a new algorithm, referred to as the "chimera" algorithm, is introduced as a key concept for proof of the separation result. The paper also provides rigorous proofs of various facts used in the study, and explores the interdependence among different algorithms and probability distributions.

Main Finding

The main finding of this paper is the identification of the collapse and separation of equilibria inequalities on AND-OR trees without shape constraints, demonstrating that randomized depth-first algorithms have the same equilibrium as directional algorithms, leading to the conclusion that there are cases where even depth-first algorithms cannot achieve the fastest results, providing a deeper understanding of the depth-first algorithm for AND-OR trees. Additionally, the introduction of the "chimera" algorithm serves as a key concept for the proof of the separation result.

Conclusion

The conclusion of this paper is that the randomized complexity with respect to depth-first algorithms equals that with respect to directional algorithms for AND-OR trees, demonstrating a collapse on equilibria RDF(T) = d(T) and a separation result on the equilibria R(T) < RDF(T) for certain AND-OR trees, providing a deeper understanding of the depth-first algorithm for AND-OR trees. Additionally, the introduction of the "chimera" algorithm serves as a key concept for the proof of the separation result.

Keywords

AND-OR trees, equilibrium values, probabilistic computations, depth-first algorithms, directional algorithms, chimera algorithm, eigen-distribution, game trees, multi-branching trees, complexity, and randomized Boolean decision trees.