TY - GEN
T1 - Algebraic decision trees and Euler characteristics
AU - Chi-Chih Yao, Andrew
N1 - Publisher Copyright:
© 1992 IEEE.
PY - 1992
Y1 - 1992
N2 - For any set S contained in Rn, let chi (S) denote its Euler characteristic. The author shows that any algebraic computation tree or fixed-degree algebraic decision tree must have height Omega (log mod chi (S) mod )for deciding the membership question of a compact semi-algebraic set S. This extends a result by A. Bjorner, L. Lovasz and A. Yao where it was shown that any linear decision tree for deciding the membership question of a closed polyhedron S must have height greater than or equal to log3 mod chi (S) mod.
AB - For any set S contained in Rn, let chi (S) denote its Euler characteristic. The author shows that any algebraic computation tree or fixed-degree algebraic decision tree must have height Omega (log mod chi (S) mod )for deciding the membership question of a compact semi-algebraic set S. This extends a result by A. Bjorner, L. Lovasz and A. Yao where it was shown that any linear decision tree for deciding the membership question of a closed polyhedron S must have height greater than or equal to log3 mod chi (S) mod.
UR - https://www.scopus.com/pages/publications/85065717612
U2 - 10.1109/SFCS.1992.267765
DO - 10.1109/SFCS.1992.267765
M3 - 会议稿件
AN - SCOPUS:85065717612
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 268
EP - 277
BT - Proceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992
PB - IEEE Computer Society
T2 - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992
Y2 - 24 October 1992 through 27 October 1992
ER -