<p>I am trying to find information about the following problem. Let <span class="math-container">$C_1$</span> and <span class="math-container">$C_2$</span> be any two poly-size arithmetic circuits on input vectors x₁ and x₂ correspondingly. Assume that a third arithmetic circuit <span class="math-container">$C_3$</span> (also poly-size) combines their outputs. To make the problem non-trivial, <span class="math-container">$C_3$</span> can have multiplicative-depth <span class="math-container">$1$</span>; however, the other two circuits have no such restrictions. What is known about the power of the resulting circuit class? Even some good keywords would help. Thanks in advance.</p>

<p>edit: forgot some details, please see my comments.</p>

CC BY-SA 4.0
2020-05-19T21:40:26.077Z
I don't understand: is the idea that $C_3(x_1,x_2) = f(C_1(x_1), C_2(x_2))$ where $f$ is computed by a circuit of multiplicative depth 1, but $C_1, C_2$ are unrestricted? You must have some restrictions on $C_1, C_2$ otherwise you just get back the class of all functions computable by poly-size arithmetic circuits...
Joshua Grochow
CC BY-SA 4.0
2020-05-19T22:22:34.293Z
Yes, that's the idea. However, forgot to say that $C_3$ can have many outputs and that each product performed by $f$ needs to have one output of $C_1$ and one output of $C_2$. The setting is that $C_i$ have private inputs, and I would like to understand what computation can be done in the case when they can spend limited circuit power in common computation (but can do poly-size precomputation).
cryptocat
CC BY-SA 4.0
2020-05-19T22:22:39.603Z
For example, one can compute efficiently scalar products of two private vectors and evaluate polynomials where one party owns the polynomial and another one the evaluation point (then $C_1$ would just output all coefficients $a_i$, $C_2$ would precompute all powers of say $x$, and then $f$ would output $\sum a_i x^i$). Intuitively, you want to avoid the blowup (where $f$ would need to multiply and then sum up too many private outputs). Also, privacy is not issue, just efficiency.
cryptocat
CC BY-SA 4.0
2020-05-20T16:11:54.753Z
I see. I think the word for $f$ to search for is "set-multilinear" or "multilinear" or "bilinear" (depending on the authors and context).
Joshua Grochow
CC BY-SA 4.0
2020-05-21T10:00:55.510Z
Thanks! Do you know if my question has a simple answer?
cryptocat
<circuit-complexity><arithmetic-circuits>
Multiplicative-depth 1 composition of arithmetic circuits
cryptocat
# Multiplicative-depth 1 composition of arithmetic circuits

(Asked by: username_0 on 2020-05-19)

I am trying to find information about the following problem. Let $C\_1$ and $C\_2$ be any two poly-size arithmetic circuits on input vectors x₁ and x₂ correspondingly. Assume that a third arithmetic circuit $C\_3$ (also poly-size) combines their outputs. To make the problem non-trivial, $C\_3$ can have multiplicative-depth $1$; however, the other two circuits have no such restrictions. What is known about the power of the resulting circuit class? Even some good keywords would help. Thanks in advance.

edit: forgot some details, please see my comments.

**Tags:** circuit-complexity, arithmetic-circuits
> **Comments:**
> **username_1**: I don't understand: is the idea that $C_3(x_1,x_2) = f(C_1(x_1), C_2(x_2))$ where $f$ is computed by a circuit of multiplicative depth 1, but $C_1, C_2$ are unrestricted? You must have some restrictions on $C_1, C_2$ otherwise you just get back the class of all functions computable by poly-size arithmetic circuits...  
> **username_0**: Yes, that's the idea. However, forgot to say that $C_3$ can have many outputs and that each product performed by $f$ needs to have one output of $C_1$ and one output of $C_2$. The setting is that $C_i$ have private inputs, and I would like to understand what computation can be done in the case when they can spend limited circuit power in common computation (but can do poly-size precomputation).  
> **username_0**: For example, one can compute efficiently scalar products of two private vectors and evaluate polynomials where one party owns the polynomial and another one the evaluation point (then $C_1$ would just output all coefficients $a_i$, $C_2$ would precompute all powers of say $x$, and then $f$ would output $\sum a_i x^i$). Intuitively, you want to avoid the blowup (where $f$ would need to multiply and then sum up too many private outputs). Also, privacy is not issue, just efficiency.  
> **username_1**: I see. I think the word for $f$ to search for is "set-multilinear" or "multilinear" or "bilinear" (depending on the authors and context).  
> **username_0**: Thanks! Do you know if my question has a simple answer?  

---

## 0 answers

