As of May 31, 2023, we have updated our Code of Conduct.

Questions tagged [decision-trees]

The tag has no usage guidance.

10 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
13 votes
0 answers

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 ...
Jardine's user avatar
  • 395
6 votes
0 answers

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'$ ...
jian's user avatar
  • 769
5 votes
0 answers

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 ...
user avatar
4 votes
0 answers

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 ...
domotorp's user avatar
  • 13.9k
4 votes
0 answers

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 ...
Sadguru's user avatar
  • 83
3 votes
0 answers

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", ...
EXPTIME-complete's user avatar
3 votes
0 answers

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 ...
user1278599's user avatar
2 votes
0 answers

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 ...
user avatar
0 votes
0 answers

Designing an appropriate training set for CART classification using imbalanced data

I'm experimenting with using CART (or maybe Random Forest) to classify genomic data. There are essentially two classes, whereof one is the 'normal' state and the other is the 'exceptional' state. Now,...
Rainer's user avatar
  • 1
-1 votes
1 answer

Time complexity analysis of random forest and k-means?

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 ...
Eric Nunes's user avatar