Questions tagged [decision-trees]
The decision-trees tag has no usage guidance.
38 questions
2
votes
0
answers
75
views
Learning a boolean function using decision tree with small number of queries
I am working on a problem and I am looking to solve the following subproblem : Given a "restrictive" blackbox access to boolean function $\phi$, output a "small-sized" CNF that ...
6
votes
0
answers
139
views
Generalization of the generalization of the evasiveness conjecture
The generalized evasiveness conjecture (Aanderaa, Rosenberg, Karp, Kahn, Saks, Sturtevant) states that any non-constant, monotone ($x\le y \Rightarrow f(x)\le f(y)$, weakly symmetric Boolean function ...
- 14.2k
5
votes
0
answers
76
views
Hardness of Computing Tribes-DNF by Decision Trees
In this paper on "The Polynomial Hierarchy, Random Oracles, and Boolean Circuits", Fact (3.2) states that it is impossible for a polylogarithmic depth decision tree to compute the Tribes-DNF ...
- 51
1
vote
1
answer
187
views
If boolean function $f$ is computable by a k-CNF and an l-DNF then it can be computed by a decision tree of depth at most kl
I have seen it stated that if boolean function $f$ is computable by a $k$-CNF and an $l$-DNF then it can be computed by a decision tree of depth at most $kl$. However, I am not able to see why this is ...
5
votes
2
answers
200
views
Lower bound for sorting without using a decision tree model
Can we prove the lower bound for the sorting problem just by Turing machine model?
It seems that available proof of sorting is based on the assumption that the algorithm only uses comparison so we can ...
- 51
4
votes
1
answer
264
views
Binary Trees for Nearest Neighbor Search
Given points $x_1, ..., x_n \in \mathbb{R}^d$, consider a binary decision tree $T$ on $\mathbb{R}^d$ with $L$ leaves, i.e. for a point $y \in \mathbb{R}^d$ at every node of the tree, we check whether $...
- 189
4
votes
0
answers
195
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 ...
- 14.2k
7
votes
1
answer
391
views
Complexity of constructing minimum depth decision trees
I am interested in the computational complexity of
Problem 1: Given a finite, non-empty set $J$, given $A, B \subseteq \{0,1\}^J$ such that $A \cap B = \emptyset$, and given $n \in \mathbb{N}$, does ...
- 193
-3
votes
1
answer
139
views
Finding the maximum no. of people who get along in a group [closed]
Suppose that there are 15 people in a room. Assume that each person gets along with other people in the room (but not everyone). (Note that the "feeling is mutual" between any two people who are ...
3
votes
0
answers
144
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", ...
- 408
4
votes
0
answers
264
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 ...
- 83
22
votes
5
answers
854
views
Easy problems with hard counting versions
Wikipedia provides examples of problems where the counting version is hard, whereas the decision version is easy. Some of these are counting perfect matchings, counting the number of solutions to $2$-...
- 13.3k
4
votes
2
answers
580
views
Lower bound on the element distinctness problem
The element distinctness problem asks whether any two elements of the input
sequence $<x_1,\ldots,x_n>$ are equal? This problem has a lower bound of
$\Omega(n \log n)$ in the algebraic decision ...
- 83
1
vote
1
answer
219
views
Randomized and deterministic query complexity of symmetric functions
The deterministic query complexity $D(f)$ of a symmetric function $f$ is $\Omega(n)$ (except for f = 0 or f = 1). I am wondering if the same result holds for the (bounded-error) randomized query ...
- 313
1
vote
1
answer
754
views
Minmax vs Maxmin
I'm reading this paper about building a combat simulator for 8 unit vs 8 unit mini combats in StarCraft: Brood War. The basic idea is to build a search tree simulating these small combats in order to ...
- 113
1
vote
1
answer
160
views
decision tree complexity and query complexity
I want good sources for starting with decision tree complexity and query complexity , what papers to start with ? what book chapters to read ? I already seen arora and barak book and I begin to read ...
5
votes
0
answers
176
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 ...
user6973
10
votes
1
answer
662
views
Canonical representation of Binary Decision Tree in Ptime?
I am wondering whether there may exist a way to give a sort of "normal form" for binary decision trees (BDT) in a tractable way.
More precisely: a BDT is a tree with internal nodes labelled by ...
- 696
2
votes
1
answer
463
views
Lower bound for finding repeated elements in sorted array
This is inspired by [1] (which still needs answers).
What is the tight lower bound (or optimal algorithms) for the "finding repeated elements" problem: Given a sorted integer array of size $n$, how ...
- 2,329
11
votes
2
answers
336
views
What is the complexity of the equivalence problem for read-once decision trees?
A read-once decision tree is defined as follows:
$True$ and $False$ are read-once decision trees.
If $A$ and $B$ are read-once decision trees and
$x$ is a variable not occurring in $A$ and $B$,
then $...
- 696
9
votes
1
answer
617
views
What is the complexity of decision tree complexity?
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 $...
- 14.2k
13
votes
0
answers
450
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 ...
- 405
24
votes
1
answer
656
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.9k
13
votes
2
answers
887
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.8k
14
votes
2
answers
657
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 ...
- 32.2k
2
votes
0
answers
159
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 ...
user6973
-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 ...
23
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?
...
- 689
3
votes
0
answers
744
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 ...
- 31
-2
votes
1
answer
320
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 ...
- 97
27
votes
1
answer
926
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\}$ ...
- 14.5k
6
votes
0
answers
287
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'$ ...
- 769
6
votes
1
answer
247
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 ...
- 163
0
votes
0
answers
96
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,...
- 1
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 ...
- 10.3k
5
votes
2
answers
916
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 ...
- 151
3
votes
1
answer
532
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 $...
- 523
0
votes
2
answers
336
views
Learning using decision trees
I have a quick question that I'm stumped on. This is about constructing a decision tree using information gain (entropy). Let's say we have a dataset with two input attributes such that the ...
user3988