<p>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]$.</p>

<p>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$? </p>

CC BY-SA 3.0
2011-09-22T13:11:53.487Z
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})$?
Bruno
CC BY-SA 3.0
2011-09-22T13:20:34.883Z
$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
Klim
CC BY-SA 3.0
2015-11-26T06:15:34.420Z
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.)
Joshua Grochow
<cc.complexity-theory><circuit-complexity>
Evaluations of arithmetic circuits
Klim
# Evaluations of arithmetic circuits

(Asked by: username_0 on 2011-09-22)

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$?

**Tags:** cc.complexity-theory, circuit-complexity
> **Comments:**
> **username_1**: 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})$?  
> **username_0**: $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  
> **username_2**: 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.)  

---

## 0 answers

