Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2502.02022 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
Inhaltsangabe:
- We study a decision tree model in which one is allowed to query subsets of variables. This model is a generalization of the standard decision tree model. For example, the $\lor-$decision (or $T_1$-decision) model has two queries, one is a bit-query and one is the $\lor$-query with arbitrary variables. We show that a monotone property graph, i.e. nontree graph is lower bounded by $n\log n$ in $T_1$-decision tree model. Also, in a different but stronger model, $T_2$-decision tree model, we show that the majority function and symmetric function can be queried in $\frac{3n}{4}$ and $n$, respectively.