AbstractWe show that any algebraic computation tree or any fixed-degree algebraic tree for solving the membership question of a compact setS⊆Rnmust have height greater thanΩ(log(βi(S)))−cnfor eachi, whereβi(S) is theith Betti number. This generalizes a well-known result by Ben-Or who proved this lower bound for the casei=0, and a recent result by Björner and Lovász who proved this lower bound for allifor linear decision trees
We introduce a new powerful method for proving lower bounds on randomized and deterministic analyti...
We propose a natural extension of algebraic decision trees to the external-memory setting, where the...
Dedicated to the memory of Roman Smolensky Abstract. We prove the first nontrivial (and superlinear)...
AbstractWe show that any algebraic computation tree or any fixed-degree algebraic tree for solving t...
AbstractFor any set S ⊆ Rn, let χ(S) denote its Euler characteristic. In this paper, we show that an...
We prove an exponential lower bound on the size of (ternary) algebraic decision trees for the MAX Pr...
AbstractIn this paper, we prove two general lower bounds for algebraic decision trees which test mem...
The first goal of this thesis is to present two different methods, originally developed by Björner, ...
We show that any parallel algorithm in the fixed degree algebraic decision tree model that answers m...
In this paper, we prove two general lower bounds for algebraic decision trees which test membership ...
In this paper, we prove two general lower bounds for algebraic decision trees which test membership ...
We describe a new method for proving lower bounds for algebraic computation trees. We prove, for the...
AbstractWe investigate the complexity of algebraic decision trees deciding membership in a hypersurf...
Abstract — We show how to approximate any function in AC0 by decision trees of much smaller height t...
AbstractWe consider the role of randomness for the decisional complexity in algebraic decision (or c...
We introduce a new powerful method for proving lower bounds on randomized and deterministic analyti...
We propose a natural extension of algebraic decision trees to the external-memory setting, where the...
Dedicated to the memory of Roman Smolensky Abstract. We prove the first nontrivial (and superlinear)...
AbstractWe show that any algebraic computation tree or any fixed-degree algebraic tree for solving t...
AbstractFor any set S ⊆ Rn, let χ(S) denote its Euler characteristic. In this paper, we show that an...
We prove an exponential lower bound on the size of (ternary) algebraic decision trees for the MAX Pr...
AbstractIn this paper, we prove two general lower bounds for algebraic decision trees which test mem...
The first goal of this thesis is to present two different methods, originally developed by Björner, ...
We show that any parallel algorithm in the fixed degree algebraic decision tree model that answers m...
In this paper, we prove two general lower bounds for algebraic decision trees which test membership ...
In this paper, we prove two general lower bounds for algebraic decision trees which test membership ...
We describe a new method for proving lower bounds for algebraic computation trees. We prove, for the...
AbstractWe investigate the complexity of algebraic decision trees deciding membership in a hypersurf...
Abstract — We show how to approximate any function in AC0 by decision trees of much smaller height t...
AbstractWe consider the role of randomness for the decisional complexity in algebraic decision (or c...
We introduce a new powerful method for proving lower bounds on randomized and deterministic analyti...
We propose a natural extension of algebraic decision trees to the external-memory setting, where the...
Dedicated to the memory of Roman Smolensky Abstract. We prove the first nontrivial (and superlinear)...
DOI
Add to ORKG