Registered Data

[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.
  • Classification : 03D15, 68Q17, 68W20
  • Format : Talk at Waseda University
  • Author(s) :
    • Fuki Ito (Tokyo Metropolitan University)
    • Fuki Ito (Tokyo Metropolitan University)