All Questions
Tagged with decision-trees boolean-functions
6 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 ...
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 ...
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
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
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