# Multiplicative-depth 1 composition of arithmetic circuits

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.

• 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 May 19 '20 at 21:40
• 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 May 19 '20 at 22:22
• 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 May 19 '20 at 22:22
• 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 May 20 '20 at 16:11