0
$\begingroup$

I am reading Depth Reduction of Arithmetic Formula form the survey of Ramprasad Saptharishi. Now in the proof of depth reduction due to Brent, 74 that

Let $f$ be an n-variate degree d polynomial computed by an arithmetic formula $\Phi$ of size s. Then, $f$ can also be computed by a formula $\Phi^{\prime}$ of size $s^{\prime}=\operatorname{poly}(s, n, d)$ and depth $O(\log s)$

In the proof they have written that

Consider the first node in this path $V$ such that the size of the formula rooted at $v$ is smaller than $\frac{2s}{3}$. Let $\Phi_v$ refer to the sub-formula rooted at $V$. By the choice of the path from the root, we have $$\frac{s}3\leq |\Phi_v|\leq \frac{2s}{3}$$

Now how are we getting the $\frac{s}3\leq |\Phi_v|$ inequality?

$\endgroup$
1

1 Answer 1

3
$\begingroup$

You do not cite the part of the survey that is actually relevant for getting the $s/3$ lower bound:

Starting from the root, walk down to the leaves by always taking the child with a larger sub-tree under it. Consider the first node in this path $v$ such that the size of the formula rooted at v is smaller than $2s/3$.

$v$ cannot be the root since the subtree rooted at the root has size $s$. Let $w$ be the predecessor of $v$. By definition, the subtree rooted at $w$ contains more than $2s/3$ nodes. Since it has most two children and $v$ is the child with the largest subtree under it, it has more than half the nodes under $w$, that is, more than $s/3$.

$\endgroup$
1
  • $\begingroup$ See also Emil's linked thread since indeed, you may not only have a value precisely between $s/3$ and $2s/3$ but between $\lceil s/3 \rceil$ and $\lceil 2s/3 \rceil$. $\endgroup$
    – holf
    Nov 8, 2022 at 8:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.