Questions tagged [decision-trees]

The tag has no usage guidance.

10 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
431 views

How can one find the "hard" probability distribution on the input for recursive boolean functions?

Update: Since, it seems there is no progress regarding this question, any idea, conjecture, hunch, or advice is welcome. For example, are there any partial or incomplete results? What are the main ...
236 views

Tree rotation, a problem similar to Huffman coding

I am not sure whether the following problem has been studied. We have a undirected tree $T$. We would like to construct another tree $T'$. $T'$ is a binary tree. Each inner nodes of $T'$ ...
169 views

The Complexity of Properly Learning Decision Trees

Where does this paper prove the middle bullet point of its abstract? I have looked through that paper fairly thoroughly. There are three things I want to read how they're getting around. Reductions ...
251 views

Algebraic decision trees and adversary arguments

In the comparison tree model, we establish lower bounds on computing $\min$ and $\max$ of $n$ numbers via the adversary argument. Are there problems on which we know lower bounds in the algebraic ...
131 views

Is it possible that the Aanderaa–Karp–Rosenberg conjecture is just a bit false?

The Aanderaa–Karp–Rosenberg conjecture is that any non-trivial monotone property on graphs is evasive. It has been proved for several special cases, but for a general graph on $n$ vertices, we only ...
138 views

Approximation class of finding decision trees with minimal depth

We are given some sets $S_1, \cdots , S_n$ and two disjoint sets $A$ and $B$. A decision tree is a binary tree where each node asks "$x \in S_i?$" for some $i$, taking the left branch means "yes", ...
585 views

Is there a tight lower bound on the complexity of SSSP on a graph?

I'm an undergrad and I'm not sure if this is the right way to ask this question. I want to know the lower bound on single-source shortest path computation in a general graph. The graph is allowed to ...
154 views

How hard is it to compute an approximately optimal non-greedy CART tree?

The question itself is closer to the bottom of this post, and is formulated without any rerefence to the term "CART". Motivation: In traditional CART (Classification and Regression Trees), one ...
I am working with random forest for a supervised classification problem, and I am using the k-means clustering algorithm to split the data at each node, where $n$ is the number of points, $K$ is ...