Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

# Questions tagged [decision-trees]

The tag has no usage guidance.

33 questions
Filter by
Sorted by
Tagged with
181 views

Given a boolean function $f$ on $n$ bits, how hard is it to determine its decision tree complexity? (I assume the decision tree is simple, i.e., the allowed questions are the bits of the input.) If $... 13 votes 0 answers 437 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 ... 23 votes 1 answer 585 views ### The randomized query complexity of the conjoined trees problem An important 2003 paper by Childs et al. introduced the "conjoined trees problem": a problem admitting an exponential quantum speedup that's unlike just about any other such problem that we know of. ... 13 votes 2 answers 841 views ### Las Vegas vs Monte Carlo randomized decision tree complexity Background: Decision tree complexity or query complexity is a simple model of computation defined as follows. Let$f:\{0,1\}^n\to \{0,1\}$be a Boolean function. The deterministic query complexity of ... 13 votes 2 answers 618 views ### Provable gaps between decision tree complexity and "true" complexity The title is a little misleading: but hopefully the question isn't: Grønlund and Pettie's new result showing that 3SUM has only$O(n^{3/2})$decision tree complexity got me wondering: Is there a ... 2 votes 0 answers 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 ... -1 votes 1 answer 2k views ### 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 ... 22 votes 3 answers 2k views ### Sorting using a black box Assume that we want to sort a list$S$of$n$real numbers. Assume that we are given a black box that can sort$\sqrt n$real numbers instantly. How much advantage can we gain using this black box? ... 3 votes 0 answers 605 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 ... -2 votes 1 answer 304 views ### Sorting : proof for lower bound of Sorting [closed] I have read the proof of lower bound of Sorting Algorithm that use comparison to know input is NlogN. In this paper, the author use decision tree for this proof. Everything on this proof I have ... 27 votes 1 answer 908 views ### Coloring complexity of graphs Suppose$G$is a graph with coloring number$d = \chi(G)$. Consider the following game between Alice and Bob. At each round, Alice picks a vertex, and Bob answers with a color in$\{1,\ldots,d-1\}$... 6 votes 0 answers 239 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'$... 6 votes 1 answer 238 views ### Is there an accepted name for Ross Quinlan's adaptation of the ID3 decision algorithm to use a Pearson's chi-squared test for independence? In Ross Quinlan's seminal paper Induction of Decision Trees, Quinlan summarizes the current state of machine learning in 1985 and loudly introduces the ID3 decision algorithm in the context of its ... 0 votes 0 answers 94 views ### 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,... 17 votes 1 answer 2k views ### Algorithm for optimizing decision trees Background A binary decision tree$T$is a rooted tree where each internal node (and root) is labeled by an index$j \in \{1,..., n\}$such that no path from root to leaf repeats an index, the leafs ... 4 votes 2 answers 751 views ### Building a decision tree to approximate a known function (not to learn an unknown function) I have a function$f: \mathbb{D} \rightarrow \{0,1\}$where$\mathbb{D} \in \mathbb{R}^{5000}$. I would like to approximate$f$using a decision tree. Up to now I have only found literature in the ... 3 votes 1 answer 450 views ### Bounds on the size of smallest decision tree for a boolean function? Consider a boolean function$f : V \rightarrow \{0,1\}$with$m$true points. Are there any non-trivial bounds in$m$on the size of the smallest decision tree for$f$? It seems to me that assuming$... 