<p>It is possible. Let <span class="math-container">$g(y)$</span> be an arbitrary non-constant boolean function (<span class="math-container">$y$</span> can be an arbitrarily long vector of boolean variables), and let
<span class="math-container">$$f(x,a_0,a_1,y)=\left\{\begin{array}{ll}
0 &amp;\textrm{if $x=0$, and $a_0=a_1$,} \\
a_{g(y)}&amp;\textrm{if $x=1$, or $a_0\neq a_1$.}
\end{array}\right.$$</span>
We have:</p>
<ul>
<li><span class="math-container">$DT(f)\leq DT(g)+2$</span>, by first querying <span class="math-container">$a_0$</span> and <span class="math-container">$a_1$</span>. If they are equal then query <span class="math-container">$x$</span>, otherwise compute <span class="math-container">$g(y)$</span>.</li>
<li><span class="math-container">$DT(f|_{x=1})\leq DT(g)+1$</span>. by first compute <span class="math-container">$g(y)$</span>, then query <span class="math-container">$a_{g(y)}$</span>.</li>
<li><span class="math-container">$DT(f|_{x=0})\geq DT(g)+2$</span>. Take the optimal decision tree <span class="math-container">$T$</span> of <span class="math-container">$f|_{x=0}$</span> which computes
<span class="math-container">$$f_{x=0}(a_0,a_1,y)=\left\{\begin{array}{ll}
0 &amp;\textrm{if $a_0=a_1$,} \\
a_{g(y)}&amp;\textrm{if $a_0\neq a_1$.}
\end{array}\right.$$</span>
Every path in <span class="math-container">$T$</span> has to query at least one of <span class="math-container">$a_0$</span> or <span class="math-container">$a_1$</span>. Without loss of generality consider a path where <span class="math-container">$a_0$</span> is first queried, we only look at the branch that <span class="math-container">$a_0=1$</span>. In this branch the function is
<span class="math-container">$$f_{x=0,a_0=1}(a_1,y)=\neg g(y)\wedge\neg a_1.$$</span>
Setting <span class="math-container">$a_1=0$</span>, each path in the branch decides the value of <span class="math-container">$g(y)$</span>, and <span class="math-container">$a_1$</span> must also be queried either on the path or at the leaf where <span class="math-container">$g(y)=0$</span>. This means that, by doing so for every path, we get a decision tree for <span class="math-container">$g$</span> where each path of length <span class="math-container">$\ell$</span> corresponds to a path of length <span class="math-container">$\ell+2$</span> in <span class="math-container">$T$</span>.</li>
</ul>
<p>Therefore we get <span class="math-container">$DT(f)=DT(f|_{x=0})=DT(g)+2&gt; DT(f|_{x=1})$</span>.</p>

CC BY-SA 4.0
2023-03-04T08:02:41.303Z
I don’t think that “every path in the decision tree has to query both $a_0$ and $a_1$” is true. If you start by computing $g(y)$ and $a_{g(y)}$, then if the latter is $0$, you know the answer is $0$ without querying $a_{1-g(y)}$.
Emil Jeřábek
CC BY-SA 4.0
2023-03-04T09:05:20.917Z
@EmilJeřábek I think that Wei Zhan is right. Let $g(y)=y$. Then $f_{x=0, y=0} = a_0 \not \to a_1$;  $f_{x=0, a_0=0} = a_1 \land y$; $f_{x=0, a_1=0} = a_0 \not \to y$.
Alexey Milovanov
CC BY-SA 4.0
2023-03-04T09:07:43.073Z
Thank you! Just an observation: $DT(g) =1$ because $g(y)=y$ or $g(y)= \neg y$ :)
Alexey Milovanov
CC BY-SA 4.0
2023-03-04T09:46:21.107Z
@AlexeyMilovanov Yes, for the special case $g(y)=y$ one can check that $DT(f\restriction_{x=0})=3$ by hand. But the argument as stated is not correct for arbitrary $g$. Since the answer says that $g$ is “an arbitrary non-constant boolean function”, I assume the intention is that $y$ is a vector of variables.
Emil Jeřábek
CC BY-SA 4.0
2023-03-04T14:27:16.940Z
Again: why “every path in the branch must also query $a_1$”? Consider the dual of my first comment: first compute $g(y)$, and query $a_{1-g(y)}$. If the latter is $1$, the answer is $0$ without needing to query $a_{g(y)}$.
Emil Jeřábek
CC BY-SA 4.0
2023-03-04T14:38:11.430Z
@EmilJeřábek Right, I also realized it soon after I made the first edit. Now it should be correct (finally!).
Wei Zhan
CC BY-SA 4.0
2023-03-04T15:12:00.450Z
I’m sorry, but I still can’t make sense of the argument. So you look at a node where $a_0$ is first queried, and consider the $a_0=1$ branch. Fine. Now, every path in this branch that’s consistent with the setting $a_1=0$ decides $g(y)$, yes. But it’s perfectly possible that some of these paths decide that $g(y)=1$ and terminate without querying $a_1$. So how can you conclude that *every* path of length $\ell$ corresponds to a path of length $\ell+2$ in $T$?
Emil Jeřábek
CC BY-SA 4.0
2023-03-04T15:40:06.993Z
@EmilJeřábek If it decides that $g(y)=1$, and the tree is optimal so no redundant query, then the last query also has an outcome that $g(y)=0$. If $a_1$ was not queried on the path, $a_1$ must be queried at this leaf.
Wei Zhan
CC BY-SA 4.0
2023-03-04T16:17:31.407Z
Oh, I see, now I get it. (There's a borderline case when the last query before the leaf is the one that queried $a_0$, but in this case it also works out.) Thank you for the explanation.
Emil Jeřábek
CC BY-SA 4.0
2023-03-04T06:55:54.833Z
2023-03-04T16:28:02.430Z
2023-03-04T16:28:02.430Z
Wei Zhan
<p>Let <span class="math-container">$f$</span> be a Boolean function. Is it possible that for some <span class="math-container">$x$</span> it holds that <span class="math-container">$DT(f|_{x=0}) = DT(f)$</span>, but <span class="math-container">$DT(f|_{x=1}) &lt; DT(f)$</span>?</p>
<p>Here <span class="math-container">$DT(f)$</span> is decision tree complexity, i.e. the minimum depth of a decision tree that computes <span class="math-container">$f$</span>.</p>

CC BY-SA 4.0
2023-03-03T22:06:24.983Z
By DT do you mean decision tree depth, or size? Do you mean for all x or there is an x?
Ryan Williams
CC BY-SA 4.0
2023-03-03T22:11:45.247Z
@RyanWilliams Depth, there is an $x$
Alexey Milovanov
<untagged>
A question about decision tree complexity
Alexey Milovanov
# A question about decision tree complexity

(Asked by: username_0 on 2023-03-03)

Let $f$ be a Boolean function. Is it possible that for some $x$ it holds that $DT(f|\_{x=0}) = DT(f)$, but $DT(f|\_{x=1}) < DT(f)$?

Here $DT(f)$ is decision tree complexity, i.e. the minimum depth of a decision tree that computes $f$.

**Tags:** untagged

> **Comments:**
> **username_1**: By DT do you mean decision tree depth, or size? Do you mean for all x or there is an x?  
> **username_0**: @RyanWilliams Depth, there is an $x$  

---

## 1 answers

### Answer by username_2 on 2023-03-04. Score: 3 | Accepted answer

It is possible. Let $g(y)$ be an arbitrary non-constant boolean function ($y$ can be an arbitrarily long vector of boolean variables), and let
$$f(x,a\_0,a\_1,y)=\left\{\begin{array}{ll}
0 &\textrm{if $x=0$, and $a\_0=a\_1$,} \\
a\_{g(y)}&\textrm{if $x=1$, or $a\_0\neq a\_1$.}
\end{array}\right.$$
We have:

* $DT(f)\leq DT(g)+2$, by first querying $a\_0$ and $a\_1$. If they are equal then query $x$, otherwise compute $g(y)$.
* $DT(f|\_{x=1})\leq DT(g)+1$. by first compute $g(y)$, then query $a\_{g(y)}$.
* $DT(f|\_{x=0})\geq DT(g)+2$. Take the optimal decision tree $T$ of $f|\_{x=0}$ which computes
  $$f\_{x=0}(a\_0,a\_1,y)=\left\{\begin{array}{ll}
  0 &\textrm{if $a\_0=a\_1$,} \\
  a\_{g(y)}&\textrm{if $a\_0\neq a\_1$.}
  \end{array}\right.$$
  Every path in $T$ has to query at least one of $a\_0$ or $a\_1$. Without loss of generality consider a path where $a\_0$ is first queried, we only look at the branch that $a\_0=1$. In this branch the function is
  $$f\_{x=0,a\_0=1}(a\_1,y)=\neg g(y)\wedge\neg a\_1.$$
  Setting $a\_1=0$, each path in the branch decides the value of $g(y)$, and $a\_1$ must also be queried either on the path or at the leaf where $g(y)=0$. This means that, by doing so for every path, we get a decision tree for $g$ where each path of length $\ell$ corresponds to a path of length $\ell+2$ in $T$.

Therefore we get $DT(f)=DT(f|\_{x=0})=DT(g)+2> DT(f|\_{x=1})$.

> **Comments:**
> **username_3**: I don’t think that “every path in the decision tree has to query both $a_0$ and $a_1$” is true. If you start by computing $g(y)$ and $a_{g(y)}$, then if the latter is $0$, you know the answer is $0$ without querying $a_{1-g(y)}$.  
> **username_0**: @EmilJeřábek I think that username_2 is right. Let $g(y)=y$. Then $f_{x=0, y=0} = a_0 \not \to a_1$;  $f_{x=0, a_0=0} = a_1 \land y$; $f_{x=0, a_1=0} = a_0 \not \to y$.  
> **username_0**: Thank you! Just an observation: $DT(g) =1$ because $g(y)=y$ or $g(y)= \neg y$ :)  
> **username_3**: @AlexeyMilovanov Yes, for the special case $g(y)=y$ one can check that $DT(f\restriction_{x=0})=3$ by hand. But the argument as stated is not correct for arbitrary $g$. Since the answer says that $g$ is “an arbitrary non-constant boolean function”, I assume the intention is that $y$ is a vector of variables.  
> **username_3**: Again: why “every path in the branch must also query $a_1$”? Consider the dual of my first comment: first compute $g(y)$, and query $a_{1-g(y)}$. If the latter is $1$, the answer is $0$ without needing to query $a_{g(y)}$.  
> **username_2**: @EmilJeřábek Right, I also realized it soon after I made the first edit. Now it should be correct (finally!).  
> **username_3**: I’m sorry, but I still can’t make sense of the argument. So you look at a node where $a_0$ is first queried, and consider the $a_0=1$ branch. Fine. Now, every path in this branch that’s consistent with the setting $a_1=0$ decides $g(y)$, yes. But it’s perfectly possible that some of these paths decide that $g(y)=1$ and terminate without querying $a_1$. So how can you conclude that *every* path of length $\ell$ corresponds to a path of length $\ell+2$ in $T$?  
> **username_2**: @EmilJeřábek If it decides that $g(y)=1$, and the tree is optimal so no redundant query, then the last query also has an outcome that $g(y)=0$. If $a_1$ was not queried on the path, $a_1$ must be queried at this leaf.  
> **username_3**: Oh, I see, now I get it. (There's a borderline case when the last query before the leaf is the one that queried $a_0$, but in this case it also works out.) Thank you for the explanation.  

---

