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.

  • $\begingroup$ 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... $\endgroup$ – Joshua Grochow May 19 '20 at 21:40
  • $\begingroup$ 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). $\endgroup$ – cryptocat May 19 '20 at 22:22
  • $\begingroup$ 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. $\endgroup$ – cryptocat May 19 '20 at 22:22
  • 1
    $\begingroup$ I see. I think the word for $f$ to search for is "set-multilinear" or "multilinear" or "bilinear" (depending on the authors and context). $\endgroup$ – Joshua Grochow May 20 '20 at 16:11
  • $\begingroup$ Thanks! Do you know if my question has a simple answer? $\endgroup$ – cryptocat May 21 '20 at 10:00

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.