[02412] Randomized algorithms of AND-OR tree calculation regarding query complexity
Session Time & Room : 4C (Aug.24, 13:20-15:00) @G301
Type : Contributed Talk
Abstract : We discuss the randomized algorithm of AND-OR tree calculation. It is known that for any nontrivial balanced AND-OR tree, there is a unique randomized input (eigen-distribution) which achieves the distributional complexity. In contrast, the dual problem has the opposite result; the optimal randomized algorithm is not unique. We extend the study on randomized algorithms to unbalanced cases and see that uniqueness still fails in most of the cases.
