TY - GEN
T1 - Decision tree complexity and betti numbers
AU - Yao, Andrew Chi Chih
N1 - Publisher Copyright:
© 1994 ACM.
PY - 1994/5/23
Y1 - 1994/5/23
N2 - We show that any algebraic computation tree or any fixed-degree algebraic tree for solving the membership question of a compact set S C Rn must have height greater than Ω(log(/β1-(S))) ⊆ rn for each i, where Pi(S) is the i-Th Betti number. This generalizes a well-known result by Ben-Or [Be83] who proved this lower bound for the case t = 0, and a recent result by Bjorner and Lovasz [BL92] who proved this lower bound for all i for linear decision trees.
AB - We show that any algebraic computation tree or any fixed-degree algebraic tree for solving the membership question of a compact set S C Rn must have height greater than Ω(log(/β1-(S))) ⊆ rn for each i, where Pi(S) is the i-Th Betti number. This generalizes a well-known result by Ben-Or [Be83] who proved this lower bound for the case t = 0, and a recent result by Bjorner and Lovasz [BL92] who proved this lower bound for all i for linear decision trees.
UR - https://www.scopus.com/pages/publications/0027940782
U2 - 10.1145/195058.195414
DO - 10.1145/195058.195414
M3 - 会议稿件
AN - SCOPUS:0027940782
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 615
EP - 624
BT - Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC 1994
PB - Association for Computing Machinery
T2 - 26th Annual ACM Symposium on Theory of Computing, STOC 1994
Y2 - 23 May 1994 through 25 May 1994
ER -