✦ LIBER ✦

Decision Tree Complexity and Betti Numbers

✍ Scribed by Andrew Chi-Chih Yao

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 381 KB
Volume: 55
Category: Article
ISSN: 0022-0000
DOI: 10.1006/jcss.1997.1495

No coin nor oath required. For personal study only.

✦ Synopsis

We show that any algebraic computation tree or any fixed-degree algebraic tree for solving the membership question of a compact set S R n must have height greater than 0(log(; i (S)))&cn for each i, where ; i (S) is the ith Betti number. This generalizes a well-known result by Ben-Or who proved this lower bound for the case i=0, and a recent result by Bjo rner and Lova sz who proved this lower bound for all i for linear decision trees. ] 1997 Academic Press Recently, Bjo rner and Lova sz [BL92] made another step towards linking ; i with computational complexity, showing that for linear decision trees 0(log ; i (S)) is a lower bound for all i 0; more precisely, they showed C 1 (S) log 3 ( i 0 ; i (S)).

In this paper, we extend [BL92] to general algebraic trees, thus giving a fairly complete answer to the question raised in [Be83] concerning the link between algebraic decision tree complexity and higher Betti numbers. We proved that, for any compact set S R n , C d (S), C(S) 0(log( i 0 ; i (S)))&cn (for all fixed d ). We also apply this article no.

📜 SIMILAR VOLUMES

Extremal Betti Numbers and Applications

Extremal Betti Numbers and Applications to Monomial Ideals

✍ Dave Bayer; Hara Charalambous; Sorin Popescu 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 163 KB

Let S = k x 1 x n be the polynomial ring in n variables over a field k, let M be a graded S-module, and let be a minimal free resolution of M over S. As usual, we define the associated (graded) Betti numbers β i j = β i j M by the formula \* The first and third authors are grateful to the NSF for

Alexander Duality Theorem and Second Bet

Alexander Duality Theorem and Second Betti Numbers of Stanley–Reisner Rings

✍ Naoki Terai; Takayuki Hibi 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 229 KB

A simplicial complex 2 on the vertex set V=[x 1 , x 2 , ..., x v ] is a collection of subsets of V such that (i) Let H i (2; k) denote the ith reduced simplicial homology group of 2 with the coefficient field k. Note that H &1 (2; k)=0 if 2{[<], H &1 ([<]; k)$k, and H i ([<]; k)=0 for each i 0. We

Tree-complete graph ramsey numbers

✍ V. Chvátal 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 50 KB

## Abstract The ramsey number of any tree of order __m__ and the complete graph of order __n__ is 1 + (__m__ − 1)(__n__ − 1).

Complexity of decision-theoretic trouble

Complexity of decision-theoretic troubleshooting

✍ Marta Vomlelová 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 141 KB

The goal of troubleshooting is to find an optimal solution strategy consisting of actions and observations for repairing a device. We assume a probabilistic model of dependence between possible faults, actions, and observations; the goal is to minimize the expected cost of repair (ECR). We show that

The decision tree polytope and its appli

The decision tree polytope and its application to sequential decision problems

✍ Art Warburton 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB 👁 1 views

This paper describes a new mathematical programming approach to sequential decision problems that have an underlying decision tree structure. The approach, based upon a characterization of strategies as extreme points of a 0-1 polytope called the 'decision tree polytope', is particularly suited to t

Decision tree analysis and real options:

Decision tree analysis and real options: a reconciliation

✍ Vasiliki Makropoulou 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB

The purpose of this paper is to demonstrate in a simple framework how decision tree analysis (DTA) and real options approach (ROA) yield the same results when markets are complete. The common scepticism regarding DTA has its roots in the incorrect assumption that one can apply the same discount rate