Assume that $C$ is an arithmetic circuit of size $s$ that computes function $f(\vec{x},\vec{y})\in C[x_1,x_2,\ldots,x_d,y_1\ldots y_n]$.

Does it always possible to find a basis $\vec{x}_1,\vec{x}_2,\ldots, \vec{x}_d$ for $C^d$ such that there exists a circuit of size $o(d)s$ which computes $d$ polynomials $f(\vec{x}_1),f(\vec{x}_2),\ldots f(\vec{x}_d)$ in $y_1,y_2,\ldots y_n$?

  • 3
    $\begingroup$ I don't get your notations. What does it mean that $f(\vec x,\vec y)\in C[x_1,\dotsc,x_d,y_1,\dotsc,y_n]$? What is $f(\vec{x_1})$? $\endgroup$ – Bruno Sep 22 '11 at 13:11
  • $\begingroup$ $f(\vec{x},\vec{y})$ just some polynomial in d+n variables. $f(\vec{x_1})$ is a polynomial in $n$ variables achieved from $f$ by substituting $\vec{x}_1$ in first $d$ coordinates $\endgroup$ – Klim Sep 22 '11 at 13:20
  • $\begingroup$ How important is it that the $\vec{x_i}$ form a basis of $\mathbb{C}^d$? That is, would you be satisfied if you could just find any d distinct vectors $\vec{x_1}, \dotsc, \vec{x_d} \in \mathbb{C}^d$ such that $f(\vec{x_1}), \dotsc, f(\vec{x}_d)$ can be computed in size $o(d)s$? (Maybe with some nontriviality condition, like no two of the $\vec{x}_i$ are scalar multiples of one another, or something like that.) $\endgroup$ – Joshua Grochow Nov 26 '15 at 6:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.