# Evaluating the multilinearization of an arithmetic circuit?

Let $p(x_1,\ldots,x_n)$ be a multi-variate polynomial with coefficients over a field $F$. The multilinearization of $p$, denoted by $\hat{p}$, is the result of repeatedly replacing each $x_i^d$ with $d > 1$ by $x_i$. The result is obviously a multilinear polynomial.

Consider the following problem: given an arithmetic circuit $C(x_1,\ldots,x_n)$ over $F$ and given field elements $a_1,\ldots,a_n$, compute $\hat{C}(a_1,\ldots,a_n)$.

Question: Assuming field-arithmetic can be done in unit time, is there a polynomial-time algorithm for this? Added later: I would also be interested in the special case where $C$ is actually a formula (a circuit of fan-out $1$).

• Why would it be equivalent to computing the output of a closed circuit? The problem I am facing is that the circuit can have disjoint paths from an input $x_i$ to several internal multiplication nodes, and evaluating each one of those internal multiplication nodes would require replacing $x_i$ by $a_i$ in one path and by $1$ in the other. In a circuit with an exponential number of paths, it looks like there is an exponential number of cases to take care of. – slimton Nov 11 '10 at 8:34
• @Kaveh: I don't get it. Look at the circuit $(x * x)$. If you just replace the node of input $x$ by a node with value $a$ and evaluate in the standard way you end up returning $a^2$ instead of $a$. Model of computation: just normal polynomial time on Turing machines. Think of the field as being $Z/3Z$ for concreteness, if you want. – slimton Nov 11 '10 at 12:01
• @Kaveh: I don't understand how such an algorithm implies what you say, but this does indeed contradict a common hypothesis in arithmetic circuit complexity: that the Permanent has no poly-sized arithmetic circuits (over fields other than F_2). Consider the polynomial $p=\prod_i(\sum_j x_{ij} y_j)$. The multilinear part $q$ of this polynomial has the property that its highest degree ($=2n$) part is just $r = y_1y_2\cdots y_n Per(x_{11},\ldots,x_{nn})$. If there is a small arithmetic circuit computing $q$, then one can show that there is a small arithmetic circuit computing $r$. – Srikanth Nov 12 '10 at 2:05
• @Srikanth: I didn't see your comment before posting my answer (which turned out to be the same construction you gave in your comment). I have since deleted my answer, and you should post your comment as an answer. – Joshua Grochow Nov 13 '10 at 0:58
• @Joshua: I have not added my comment as an answer since I don't understand why Kaveh's construction works. I see that the arithmetic circuit computes a polynomial that agrees with the multilinearization at all inputs, but I am not sure that it computes formally the multilinearization of the given polynomial (see my comments after Kaveh's answer). My construction (and yours) assumes that the multilinearization is computed formally. – Srikanth Nov 13 '10 at 2:43

In the case that the field $F$ is of size at least $2n$, I think this problem is hard. More specifically, I think that if the above can be efficiently solved for $F$ this large, then CNF-SAT has efficient randomized algorithms. Say we are given a CNF formula $\varphi$. One can easily come up with an arithmetic circuit $C$ that computes an arithmetization'' $p$ of $\varphi$, where the polynomial $p$ agrees with the formula $\varphi$ on $0$-$1$ inputs. Consider the multilinearization $q$ of $p$. Note that $q$ agrees with $p$ and hence $\varphi$ on $\{0,1\}^n$.

I claim that $q$ is non-zero iff $\varphi$ is satisfiable. Clearly, if $q=0$, then $\varphi$ cannot be satisfied. For the converse, one can show that any non-zero multilinear polynomial cannot vanish on all of $\{0,1\}^n$. This implies that a non-zero $q$ (and hence the corresponding $\varphi$) does not vanish at some input in $\{0,1\}^n$.

Therefore, checking for satisfiability of $\varphi$ is equivalent to checking if $q$ is non-zero. Say, now, that we could evaluate $q$ over a large field $F$. Then, using the Schwartz-Zippel Lemma, we could identity-test $q$ using an efficient randomized algorithm and check if it is the zero polynomial (the size of $F$ is used to upper bound the error in the Schwartz-Zippel Lemma).

• It seems to me that F is a fixed field because there is nothing in the input that specifies F. Also note that the question assumes that field operations take unit time. – Kaveh Nov 11 '10 at 7:37
• Thanks Srikanth. As Kaveh guessed I was indeed interested in the fixed finite field case, but this answer you gave helps me understand the question a bit better. – slimton Nov 11 '10 at 8:24

Assume that there is polytime algorithm that given $C(\vec{x}) \in F(\vec{x})$ and $\vec{a}$ computed the result of the multi-linearization of $C$ on $\vec{a}$. (w.l.o.g. I will assume that the output $\vec{b}$ will be a vector of $p$-bit binary numbers $b_i$ is $k$ iff the $b_{i,k}$ is one.)

Since $P \subseteq P/poly$, there is a polysize boolean circuit that given the encoding of the arithmetic circuit and the values for the variables computes the multi-linearization of the arithmetic circuit on the inputs. Let call this circuit $M$.

Let $C$ be an arbitrary arithmetic circuit. Fix the variables of the boolean circuit $M$ which describe the arithmetic circuit, so we have a boolean circuit computing the multi-linearization of $C$ on given inputs.

We can turn this circuit into an arithmetic circuit over $F_p$ by noting that $x^{p-1}$ is $1$ for all values but $0$ so first raise all inputs to the power $p-1$. Replace each $f \land g$ gate by multiplication $f.g$, each $f \lor g$ gate by $f+g-f.g$ and each $\lnot f$ gate by $1-f$.

By the assumption we made above about the format of the output, we can turn the output from binary to values over $F_p$. Take the output for $b_i$ and combine them to get $\sum_{0 \leq k \leq p-1}{kb_{i,k}}$.

We can also convert the input given as values over $F_p$ to binary form since there are polynomials passing through any finite number of points. E.g. if we are working in $\bmod 3$, consider the polynomials $2x(x+1)$ and $2x(x+2)$ which give the first and the second bits of the input $x \in F_3$.

Combining these we have an arithmetic circuit over $F_p$ computing the multi-linearization of $C$ with size polynomail in the size of $C$.

• It is not clear to me why the arithmetic circuit you have described computes the multilinearization of $C$, or indeed even a multilinear polynomial. I am only able to see that the arithmetic circuit computes some polynomial that agrees with the multilinearization of $C$ on $0$-$1$ inputs. – Srikanth Nov 12 '10 at 6:01
• @Srikanth: the arithmetic version of the boolean circuit $M$ (with some inputs fixed) computes the multilinear version of $C$, it doesn't need to be a multilinear. Then the only problem is that input/output are in binary not values over $F_p$, so I just need to fix the encoding for input/output from binary to original input and output values. The resulting circuit is an arithmetic circuit that gets the values for variables of $C$, encodes them in binary, computes the value of the multilinearization of $C$ over those inputs and output the answer in binary, and then translate them back to $F_p$. – Kaveh Nov 12 '10 at 6:51
• [continued] The result it is an arithmetic circuit with the same variables that $C$ has, and with the same outputs, and it is computing the multilinearization of $C$. – Kaveh Nov 12 '10 at 6:58
• @Kaveh: Have you assumed that the input to the boolean circuit $M$ is of the same form as the output of $M$? In any case, I am still not convinced. It is perfectly possible for an arithmetic circuit to compute a polynomial $f$ that agrees with a polynomial $g$ at all inputs from the field and yet $f\neq g$. For example, the polynomial $x^p$ agrees with $x$ at all inputs, and yet they are not equal as polynomials. How do you know that the circuit $M$ is not simply computing a non-multilinear polynomial that agrees with the multilinearization of $C$ at all inputs? – Srikanth Nov 12 '10 at 7:15
• @Srikanth: I have described the form of input and output in my answer. The input to $M$ is in binary, the output of $M$ is in the form stated above. I haven't said that it is multilinear, I have only said that it computes the multilinearization of the $C$. – Kaveh Nov 12 '10 at 9:47