@inproceedings{6dd3c10393164f67b6b71ece32d411ce,
title = "The computational complexity of game trees by eigen-distribution",
abstract = "The AND-OR tree is an extremely simple model to compute the read-once Boolean functions. For an AND-OR tree, the eigen-distribution is a special distribution on random assignments to the leaves, such that the distributional complexity of the AND-OR tree is achieved. Yao's Principle[8] showed that the randomized complexity of any function is equal to the distributional complexity of the same function. In the present work, we propose an eigen-distribution- based technique to compute the distributional complexity of read-once Boolean functions. Then, combining this technique and Yao's Principle, we provide a unifying proof way for some well-known results of the randomized complexity of Boolean functions.",
author = "Liu, {Chen Guang} and Kazuyuki Tanaka",
year = "2007",
doi = "10.1007/978-3-540-73556-4_34",
language = "英语",
isbn = "9783540735557",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "323--334",
booktitle = "Combinatorial Optimization and Applications - First International Conference, COCOA 2007, Proceedings",
note = "1st International Conference on Combinatorial Optimization and Applications, COCOA 2007 ; Conference date: 14-08-2007 Through 16-08-2007",
}