Eigen-distribution on assignments for game trees with random properties

Chenguang Liu; Kazuyuki Tanaka

doi:10.1145/1244002.1244020

Eigen-distribution on assignments for game trees with random properties

Chenguang Liu
, Kazuyuki Tanaka

Tohoku University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

In this paper, we investigate a special distribution, called eigen-distribution, on assignments for game tree Tk 2 with random properties. There are two cases, where the assignments to leaves are independently distributed (ID) and correlated istributed (CD). In ID setting, we prove that the distributional probability % belongs to [√7-1/3, √5-1/2 ], and q is a strictly increasing function on rounds kε² [1,1). In CD setting, we propose a reverse assigning technique (RAT) to form 1-set and 0-set, then show that E1-distribution (namely, a particular distribution on assignments of 1-set such that the complexity of any deterministic algorithm is equal) is the unique eigen-distribution.

Original language	English
Title of host publication	Proceedings of the 2007 ACM Symposium on Applied Computing
Publisher	Association for Computing Machinery
Pages	78-79
Number of pages	2
ISBN (Print)	1595934804, 9781595934802
DOIs	https://doi.org/10.1145/1244002.1244020
State	Published - 2007
Externally published	Yes
Event	22nd Annual ACM Symposium on Applied Computing, SAC 2007 - Seoul, Korea, Republic of Duration: 11 Mar 2007 → 15 Mar 2007

Publication series

Name	Proceedings of the ACM Symposium on Applied Computing

Conference

Conference	22nd Annual ACM Symposium on Applied Computing, SAC 2007
Country/Territory	Korea, Republic of
City	Seoul
Period	11/03/07 → 15/03/07

Keywords

Computational complexity
Distributional complexity
Eigen-distribution
Game trees
Randomized algorithms

Access to Document

10.1145/1244002.1244020

Cite this

@inproceedings{8cdab010d6ea4028b68ae76a228c5293,

title = "Eigen-distribution on assignments for game trees with random properties",

abstract = "In this paper, we investigate a special distribution, called eigen-distribution, on assignments for game tree Tk 2 with random properties. There are two cases, where the assignments to leaves are independently distributed (ID) and correlated istributed (CD). In ID setting, we prove that the distributional probability \% belongs to [√7-1/3, √5-1/2 ], and q is a strictly increasing function on rounds kε2 [1,1). In CD setting, we propose a reverse assigning technique (RAT) to form 1-set and 0-set, then show that E1-distribution (namely, a particular distribution on assignments of 1-set such that the complexity of any deterministic algorithm is equal) is the unique eigen-distribution.",

keywords = "Computational complexity, Distributional complexity, Eigen-distribution, Game trees, Randomized algorithms",

author = "Chenguang Liu and Kazuyuki Tanaka",

year = "2007",

doi = "10.1145/1244002.1244020",

language = "英语",

isbn = "1595934804",

series = "Proceedings of the ACM Symposium on Applied Computing",

publisher = "Association for Computing Machinery",

pages = "78--79",

booktitle = "Proceedings of the 2007 ACM Symposium on Applied Computing",

note = "22nd Annual ACM Symposium on Applied Computing, SAC 2007 ; Conference date: 11-03-2007 Through 15-03-2007",

}

Liu, C & Tanaka, K 2007, Eigen-distribution on assignments for game trees with random properties. in Proceedings of the 2007 ACM Symposium on Applied Computing. Proceedings of the ACM Symposium on Applied Computing, Association for Computing Machinery, pp. 78-79, 22nd Annual ACM Symposium on Applied Computing, SAC 2007, Seoul, Korea, Republic of, 11/03/07. https://doi.org/10.1145/1244002.1244020

Eigen-distribution on assignments for game trees with random properties. / Liu, Chenguang; Tanaka, Kazuyuki.
Proceedings of the 2007 ACM Symposium on Applied Computing. Association for Computing Machinery, 2007. p. 78-79 (Proceedings of the ACM Symposium on Applied Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Eigen-distribution on assignments for game trees with random properties

AU - Liu, Chenguang

AU - Tanaka, Kazuyuki

PY - 2007

Y1 - 2007

N2 - In this paper, we investigate a special distribution, called eigen-distribution, on assignments for game tree Tk 2 with random properties. There are two cases, where the assignments to leaves are independently distributed (ID) and correlated istributed (CD). In ID setting, we prove that the distributional probability % belongs to [√7-1/3, √5-1/2 ], and q is a strictly increasing function on rounds kε2 [1,1). In CD setting, we propose a reverse assigning technique (RAT) to form 1-set and 0-set, then show that E1-distribution (namely, a particular distribution on assignments of 1-set such that the complexity of any deterministic algorithm is equal) is the unique eigen-distribution.

AB - In this paper, we investigate a special distribution, called eigen-distribution, on assignments for game tree Tk 2 with random properties. There are two cases, where the assignments to leaves are independently distributed (ID) and correlated istributed (CD). In ID setting, we prove that the distributional probability % belongs to [√7-1/3, √5-1/2 ], and q is a strictly increasing function on rounds kε2 [1,1). In CD setting, we propose a reverse assigning technique (RAT) to form 1-set and 0-set, then show that E1-distribution (namely, a particular distribution on assignments of 1-set such that the complexity of any deterministic algorithm is equal) is the unique eigen-distribution.

KW - Computational complexity

KW - Distributional complexity

KW - Eigen-distribution

KW - Game trees

KW - Randomized algorithms

UR - https://www.scopus.com/pages/publications/35248827561

U2 - 10.1145/1244002.1244020

DO - 10.1145/1244002.1244020

M3 - 会议稿件

AN - SCOPUS:35248827561

SN - 1595934804

SN - 9781595934802

T3 - Proceedings of the ACM Symposium on Applied Computing

SP - 78

EP - 79

BT - Proceedings of the 2007 ACM Symposium on Applied Computing

PB - Association for Computing Machinery

T2 - 22nd Annual ACM Symposium on Applied Computing, SAC 2007

Y2 - 11 March 2007 through 15 March 2007

ER -

Eigen-distribution on assignments for game trees with random properties

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this