<p>&quot;Black box access&quot; to the derivative means the ability to compute it at any point of your choosing.  This procedure gives you a way to compute the derivative at any single point of your choosing.  If you want to know it for another point, repeat the procedure for that other point.  That's what &quot;black box access&quot; means.</p>

CC BY-SA 4.0
2022-01-31T05:43:11.367Z
2022-01-31T17:52:19.320Z
2022-01-31T17:52:19.320Z
D.W.
<p>This question came when reading a paper <a href="https://eccc.weizmann.ac.il/report/2011/061/download/" rel="nofollow noreferrer">here</a> about affine projections of polynomials.</p>
<p>The publisher claims in Proposition 22 that</p>
<blockquote>
<p>Let <span class="math-container">$f(\mathbf{x}) \in F[\mathbf{x}]$</span> be an <span class="math-container">$n$</span>-variate polynomial of degree <span class="math-container">$d$</span>. Given
black box access to <span class="math-container">$f$</span>, in time <span class="math-container">$poly(dn)$</span>, we obtain black box
access to any derivative <span class="math-container">$\frac{\partial f}{\partial x_i}$</span>.</p>
</blockquote>
<p>And the proof goes as follows</p>
<blockquote>
<p>Without loss of generality we can assume <span class="math-container">$i = 1$</span>. Let <span class="math-container">$a = (a_1,
 \dots, a_n) \in F^n$</span> be the point at which we want the value of
<span class="math-container">$\frac{\partial f}{\partial x_i}$</span>.  Consider <span class="math-container">$\hat f(x_1) := f(x_1 +
 a_1, a_2, \dots, a_n)$</span>. Then <span class="math-container">$\hat f(x_1)$</span> can be computed via
interpolation. Finally <span class="math-container">$$\frac{\partial f}{\partial x_1}(\mathbf{a}) = \frac{\partial \hat f}{\partial x_1}(0, \dots, 0)$$</span></p>
</blockquote>
<p>(Ignoring the error on the partial derivative of a univariate function in the paper); my question which I don't seem to understand is how does that give access to the derivatives of <span class="math-container">$f(\mathbf{x})$</span>? This only gives the derivative at a single point in <span class="math-container">$d+1$</span> queries to the blackbox at a single point and not at any point.</p>
<p>I am assuming it got something to do with looking at the extension field <span class="math-container">$F(x_2, \dots, x_n)[x_1]$</span> where <span class="math-container">$x_i$</span>'s are elements. But this still gives the derivative at the hyperplane <span class="math-container">$(a_1, F, F, \dots, F)$</span>, how does that translate to a derivative at any point in <span class="math-container">$F^n$</span>?</p>

CC BY-SA 4.0
2022-01-30T20:56:26.997Z
Now that I am thinking about it, my last comment also doesn't make any sense since we can query at a point and we can't query with variables $x_i$.
Rab
<polynomials><polynomial-time>
Interpolation to find polynomial multivariate derivative
Rab
# Interpolation to find polynomial multivariate derivative

(Asked by: username_0 on 2022-01-30)

This question came when reading a paper [here](https://eccc.weizmann.ac.il/report/2011/061/download/) about affine projections of polynomials.

The publisher claims in Proposition 22 that

> Let $f(\mathbf{x}) \in F[\mathbf{x}]$ be an $n$-variate polynomial of degree $d$. Given
> black box access to $f$, in time $poly(dn)$, we obtain black box
> access to any derivative $\frac{\partial f}{\partial x\_i}$.

And the proof goes as follows

> Without loss of generality we can assume $i = 1$. Let $a = (a\_1,
> \dots, a\_n) \in F^n$ be the point at which we want the value of
> $\frac{\partial f}{\partial x\_i}$. Consider $\hat f(x\_1) := f(x\_1 +
> a\_1, a\_2, \dots, a\_n)$. Then $\hat f(x\_1)$ can be computed via
> interpolation. Finally $$\frac{\partial f}{\partial x\_1}(\mathbf{a}) = \frac{\partial \hat f}{\partial x\_1}(0, \dots, 0)$$

(Ignoring the error on the partial derivative of a univariate function in the paper); my question which I don't seem to understand is how does that give access to the derivatives of $f(\mathbf{x})$? This only gives the derivative at a single point in $d+1$ queries to the blackbox at a single point and not at any point.

I am assuming it got something to do with looking at the extension field $F(x\_2, \dots, x\_n)[x\_1]$ where $x\_i$'s are elements. But this still gives the derivative at the hyperplane $(a\_1, F, F, \dots, F)$, how does that translate to a derivative at any point in $F^n$?

**Tags:** polynomials, polynomial-time

> **Comments:**
> **username_0**: Now that I am thinking about it, my last comment also doesn't make any sense since we can query at a point and we can't query with variables $x_i$.  

---

## 1 answers

### Answer by username_1 on 2022-01-31. Score: 2 | Accepted answer

"Black box access" to the derivative means the ability to compute it at any point of your choosing. This procedure gives you a way to compute the derivative at any single point of your choosing. If you want to know it for another point, repeat the procedure for that other point. That's what "black box access" means.


---

